Хотелось бы узнать решения задач 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; }
2022 решаю так:пусть T-момент прыжка; до него движение описывается так: x(t)=vx * t y(t)=vy * t — g*t*t/2; чтобы прыжок можно было совершить, необходимы условия: x(T)<L, y(T)>0, T>0, откуда получаем интервал для T; далее полёт описывается так: x(t')=x(T) + (vx+ux) * t', y(t')=y(T) + (vy-g*T+uy)*t' — g*t'*t'/2; теперь необходимые условия пролёта через дырку выглядят так: в момент пролёта t1 через стену (т.е. когда x(t1)=x(T)+(vx+ux)*t1=L) в т. L нужно h<y(t1)<h+d, в момент пролёта t2 через стену (т.е. когда x(t2)=x(T)+(vx+ux)*t2=L+l) в т. L нужно h<y(t2)<h+d, (3) а также если максимальная высота ф-ии y(t') достигается на [t1, t2], то max(t')<h+d. В итоге получаем некоторые интервалы решений (возникающие при решении неравенств), их пересекаем; потом (если выполняется (3), то некоторые из них обрезаем. Ответ=середина интервала длины не меньше 0.000001
Код : писать не буду, т.к. сдавал без (3), а с (3) даже инпут не прохожу.
1655 решаю так