Хотелось бы узнать решения задач http://acm.timus.ru/problem.aspx?space=1&num=1890 http://acm.timus.ru/problem.aspx?space=1&num=1839 http://acm.timus.ru/problem.aspx?space=1&num=2022 http://acm.timus.ru/problem.aspx?space=1&num=1655

везде имею WA 1890 решаю так: строю HLD; имею 2 дерева отрезков: для суммы прибавок в департаментах (до корня) (с запросами изменить значение элемента и найти сумму на отрезке) и для суммы всех индивидуальных прибавок сотрудникам в корне с заданной вершиной (с запросами найти суммарную прибавку в элементе и прибавить значение на отрезок). есть подозрения, что плохо считываю данные или имею переполнение типов

код:

include

pragma comment(linker, "/STACK:46777216")

include

using namespace std;

define ll unsigned long long

const int MAXN = 50005;

struct SegmentTree_Dep { ll * dep;
int size;

void init(int sz) 
{
    dep = new ll[4 * sz];
    memset(dep, (ll)0, 4 * sz * sizeof(ll));
    size = sz;
}

ll getSum(int v, int tl, int tr, int l, int r) 
{
    if(tl == l && tr == r) return dep[v];
    int mid = (tl + tr) >> 1, u=(v<<1);
    if(r<=mid) return getSum(u, tl, mid, l, r);
    if(l>mid) return getSum(u + 1, mid+1, tr, l, r);
    return getSum(u, tl, mid, l, mid) + getSum(u + 1, mid+1, tr, mid+1, r);
}

ll getSum(int l, int r) {return getSum(1, 1, size, l, r);}

void update(int v, int tl, int tr, int pos, ll val) 
{
    if(tl == tr) dep[v]+=val;
    else
    {
        int mid = (tl + tr) / 2, u=(v<<1);
        if(pos<=mid) update(u, tl, mid, pos, val);
        else update(u + 1, mid + 1,  tr, pos, val);
        dep[v] = dep[u] + dep[u + 1];
    }
}

void update(int pos, ll val) {update(1, 1, size, pos, val);}

};

struct SegmentTree_Sum { ll * sum; int size;

void init(int sz) 
{
    sum = new ll[4 * sz];
    memset(sum, (ll)0, 4 * sz * sizeof(ll));
    size = sz;
}

ll getVal(int v, int tl, int tr, int pos)
{
    if(tl == tr) return sum[v];
    int mid = (tl + tr) >> 1, u=(v<<1);
    if(pos<=mid) return sum[v]+getVal(u, tl, mid, pos);
    else return sum[v]+getVal(u + 1, mid+1, tr, pos);
}

ll getVal(int pos) {return getVal(1, 1, size, pos);}

void update(int v, int tl, int tr, int l, int r, ll val) 
{
    if(tl ==l && tr==r) sum[v]+=val;
    else
    {
        int mid = (tl + tr) >> 1, u=(v<<1);
        if(r<=mid) update(u, tl, mid, l, r, val);
        else
        {
           if(l>mid) return update(u+1, mid+1, tr, l, r, val);
           else update(u, tl, mid, l, mid, val), update(u+1, mid+1, tr, mid+1, r, val);
        }
    }
}

void update(int l, int r, ll val) {update(1, 1, size, l, r, val);}

};

int n, q, x, chainNum; ll y, z, sz[MAXN], s[MAXN], val[MAXN]; char c[15]; vector g[MAXN]; int p[MAXN], chain[MAXN], chainRoot[MAXN], chainSize[MAXN], chainPos[MAXN]; SegmentTree_Dep dep[MAXN]; SegmentTree_Sum sum[MAXN];

bool isHeavy(int from, int to) {return sz[to] * (ll)2 >= sz[from];}

void dfs(int v, int par = -1) { p[v] = par, sz[v] = (ll)1; for (int i = 0; i < (int) g[v].size(); i++) { int to = g[v][i]; if (to == par) continue; dfs(to, v); sz[v] += sz[to]; s[v] += s[to]; } }

int newChain(int root) { chainNum++; chainRoot[chainNum] = root; return chainNum; }

void buildHLD(int v, int curChain) { chain[v] = curChain; chainSize[curChain]++; chainPos[v] = chainSize[curChain];

for (int i = 0; i < g[v].size(); i++) 
{
    int to = g[v][i];
    if (to == p[v]) continue;
    if (isHeavy(v, to)) buildHLD(to, curChain);
    else buildHLD(to, newChain(to));
}

}

int main() { scanf("%d %d %lld", &n, &q, &val[1]); s[1]=val[1]; for (int i = 2; i <= n; i++) { scanf("%d %lld\n", &x, &val[i]); s[i]=val[i]; x++; g[x].push_back(i); g[i].push_back(x); }

dfs(1);
chainNum = 0;
buildHLD(1, newChain(1));

for (int i = 1; i <= chainNum; i++)
{
   dep[i].init(chainSize[i]); 
   sum[i].init(chainSize[i]);
}


for (int i = 1; i <= q; i++) 
{
    scanf("%s ",&c);
    if (c[0] == 'e') 
    {
        scanf("%d %lld %lld\n", &x, &y, &z);
        x++;
        int v=x;
        ll salary=val[v];
        while(v!=-1)
        {
           int curChain=chain[v];
           salary+=dep[curChain].getSum(1, chainPos[v]);
           v = p[chainRoot[curChain]];
        }
        if(salary<y)
        {
           val[x]+=z;
           while(x!=-1)
           {
              int curChain=chain[x];
              sum[curChain].update(1, chainPos[x], z);
              x = p[chainRoot[curChain]];
           }
        }
    }
    else
    {
       scanf("%d %lld %lld\n", &x, &y, &z);
       x++;
       int v=x;
       ll departament=s[v], all=(ll)0;
       while(v!=-1)
       {
           int curChain=chain[v];
           all+=dep[curChain].getSum(1, chainPos[v]);
           v = p[chainRoot[curChain]];
       }
       departament+=all*sz[x] + sum[chain[x]].getVal(chainPos[x]);
       if(departament<y*sz[x]) dep[chain[x]].update(chainPos[x], z);
    }
}

for(int i=1;i<=n;i++)
{
   int v=i;
   ll salary=val[v];
   while(v!=-1)
   {
     int curChain=chain[v];
     salary+=dep[curChain].getSum(1, chainPos[v]);
     v = p[chainRoot[curChain]];
   }
   printf("%lld", salary);
   if(i<n) printf("\n");
}

return 0;

}

1839 решаю так: перебираю дуги и для каждой ищу рожицы: во-первых отсеим все неподходящие точки без условия 4); получим претендентов Pret; теперь проблема только с условием 4). Рассмотрим очередную точку Х из Pret; для неё нужно найти все такие Y из Pret, что cos(YRP)<cos(XRP) и cos(YPR)>cos(XPR); это можно сделать за логарифм для каждой точки Х с помощью ДО.

Код:

define _CRT_SECURE_NO_WARNINGS

include

include

include

include

using namespace std;

struct Point { double x, y; bool operator > (Point Q){return x>Q.x;} bool operator < (Point Q){return x<Q.x;} };

const double eps = 0.0000001; const int nmax = 105; const int mmax = 10005;

Point P[nmax], Q[nmax], R[nmax], T[mmax]; long long n, m, r, ans; Point Ang[mmax]; int Tree[4*mmax];

double min(double x, double y){return x<y?x:y;}

void Create(int v, int tl, int tr) { if(tl==tr) Tree[v]=0; else { int m=(tl+tr)/2; Create(2*v,tl,m); Create(2*v+1,m+1,tr); } }

void Update(int v, int tl, int tr, int i) { if(tl==tr) Tree[v]++; else { int m=(tl+tr)/2; if(i<=m) Update(2*v, tl, m, i); else Update(2*v+1, m+1, tr, i); Tree[v]++; } }

int Sum(int v, int tl, int tr, int l, int r) { if(tl==tr) return Tree[v]; else { int m=(tl+tr)/2; if(r<=m) return Sum(2*v, tl, m, l, r); if(l>m) return Sum(2*v+1, m+1, tr, l, r); return Sum(2*v, tl, m, l, m)+Sum(2*v+1, m+1, tr, m+1,r); } }

double Scalar(Point P, Point Q) { return P.x*Q.x+P.y*Q.y; }

double Dist(Point A, Point B) { double dx=A.x-B.x, dy=A.y-B.y; return sqrt(dx*dx+dy*dy); }

bool GoodPoint(Point A, Point P, Point Q, Point R) { double a=R.y-P.y, b=P.x-R.x, c=R.x*P.y-P.x*R.y; double la=a*A.x+b*A.y+c, lq=a*Q.x+b*Q.y+c; Point PA, PR, RA, RP; PA.x=A.x-P.x, A.y-P.y; PR.x=R.x-P.x, R.y-P.y; RA.x=A.x-R.x, A.y-R.y; RP.x=P.x-R.x, P.y-R.y; return la*lq<0 && Scalar(PA,PR)>0 && Scalar(RA,RP)>0 && la<2.0*Dist(P,R)*sqrt(a*a+b*b); }

void QSort(Point A[], int L, int R) { int i=L, j=R; Point X=A[(L+R)/2], Y; while(i<=j) { while(A[i]<X) i++; while(A[j]>X) j--; if(i<=j) { Y=A[i], A[i]=A[j], A[j]=Y; i++, j--; } } if(L<j) QSort(A, L, j); if(i<R) QSort(A, i, R); }

double Cos(Point A, Point B) { double d1=sqrt(A.x*A.x+A.y*A.y); double d2=sqrt(B.x*B.x+B.y*B.y); return Scalar(A,B)/(d1*d2); }

int main() { scanf("%lld%lld",&n,&m);

for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf%lf%lf",&P[i].x,&P[i].y,&Q[i].x,&Q[i].y,&R[i].x,&R[i].y);

for(int j=1;j<=m;j++) scanf("%lf%lf",&T[j].x,&T[j].y);

ans=0;

for(int i=1;i<=n;i++) { r=0; for(int j=1;j<=m;j++) { if(GoodPoint(T[j], P[i], Q[i], R[i])) { Point RP, RT, PR, PT; RP.x=P[i].x-R[i].x, RP.y=P[i].y-R[i].y; RT.x=T[j].x-R[i].x, RT.y=T[j].y-R[i].y; PR.x=R[i].x-P[i].x, PR.y=R[i].y-P[i].y; PT.x=T[j].x-P[i].x, PT.y=T[j].y-P[i].y; r++; Ang[r].x=Cos(RP, RT); Ang[r].y=Cos(PR, PT); } } if(r>0) { QSort(Ang, 1, r); int N=0; map<double,int> Map; set Set; for(int j=1;j<=r;j++) Set.insert(Ang[j].y); Create(1, 1, Set.size()); for(set::iterator it=Set.begin();it!=Set.end();it++) { N++; Map.insert(make_pair(*it,N)); } int k=1; long long bad=0; ans+=r*(r-1)/2; for(int j=1;j<=r;j++) { while(k<=r && fabs(Ang[j].y-Ang[k].y)<eps) { map<double,int>::iterator it=Map.find(Ang[k].y); Update(1, 1, N, it->second); k++; } map<double,int>::iterator it=Map.find(Ang[j].y); ans-=(Sum(1, 1, N, 1, it->second)-1); } } }

printf("%lld",ans);

return 0; }