JOI春合宿2012 Day4
Copy and Paste むずすぎ・・・
2完ゲーッ
Chinese
けっこう面倒。
#include <cstdio> #include <deque> #include <algorithm> using namespace std; struct seg_tree { static const int DEPTH=18, SZ=1<<DEPTH; int data[SZ*2]; seg_tree() { for(int i=0;i<SZ*2;i++) data[i] = 1000000000; } void init(int* d, int ln) { for(int i=0;i<ln;i++) data[i+SZ] = d[i]; for(int i=ln;i<SZ;i++) data[i+SZ] = 1000000000; for(int i=SZ-1;i>=1;i--) data[i] = min(data[i*2], data[i*2+1]); } int query(int qL, int qR) { qL += SZ; qR += SZ; int ret = 1000000000; while(qL != qR){ if(qL&1) ret = min(ret, data[qL++]); if(qR&1) ret = min(ret, data[--qR]); qL >>= 1; qR >>= 1; } return ret; } }; int N, A[100000]; int ret[100000]; void solveA() { deque<int> dq; for(int i=1;i<N;i++) dq.push_back((A[i] - i + N) % N); sort(dq.begin(), dq.end()); for(int i=0;i<N;i++){ //rotate while(dq.front() < i){ dq.push_back(dq.front() + N); dq.pop_front(); } int tmp = min(i, N-i); tmp += dq.back() - i; //ret[(N-i)%N] = min(ret[(N-i)%N], tmp); ret[i] = min(ret[i], tmp); } } void solveB() { deque<int> dq; for(int i=1;i<N;i++) dq.push_back((N - (A[i] - i)) % N); sort(dq.begin(), dq.end()); for(int i=0;i<N;i++){ //rotate while(dq.front() < i){ dq.push_back(dq.front() + N); dq.pop_front(); } int tmp = min(i, N-i); tmp += dq.back() - i; ret[(N-i)%N] = min(ret[(N-i)%N], tmp); //ret[i] = min(ret[i], tmp); } } int val[200000]; int d1[200000], d2[200000]; seg_tree seg1, seg2; void solveC() { for(int i=1;i<N;i++) val[i-1] = ((A[i]-i)+N)%N; sort(val, val+(N-1)); for(int i=0;i<N-1;i++) val[i+N-1] = val[i] + N; for(int i=0;i<2*N-3;i++){ d1[i] = 2*val[i]-val[i+1]; d2[i] = val[i]-2*val[i+1]; } seg1.init(d1, 2*N-3); seg2.init(d2, 2*N-3); int left = 0; for(int i=0;i<N;i++){ while(val[left]-i < 0) left++; int tmp = 1000000000; tmp = min(tmp, seg1.query(left, left+N-2) + (N) - i); tmp = min(tmp, seg2.query(left, left+N-2) + 2*(N) + i); //printf("%d %d\n", i, tmp); ret[i%N] = min(ret[i%N], tmp + min(i, N-i)); } } int main() { scanf("%d", &N); for(int i=1;i<N;i++){ scanf("%d", A+i); --A[i]; } for(int i=0;i<N;i++) ret[i] = 2100000000; solveA(); solveB(); solveC(); for(int i=0;i<N;i++) printf("%d\n", ret[i]); return 0; }
Copy and Paste
わからなかったから平方分割書いたらバグって絶望
Invitation
シミュレーションを Segment Tree を使って高速化した。
#include <cstdio> #include <algorithm> using namespace std; const int MAX = 100000; typedef long long i64; struct range_tree { struct node { node *back, *next; int id; }; static const int DEPTH=19, SZ=1<<DEPTH; node pool[80 * MAX + 2*SZ]; int pLast; node* data[2*SZ]; int ileft[MAX*2], iright[MAX*2]; range_tree() { pLast = 0; for(int i=0;i<2*SZ;i++){ data[i] = &(pool[pLast++]); data[i]->back = data[i]->next = NULL; } for(int i=0;i<MAX;i++) ileft[i] = iright[i] = -1; } void append(int pos, int id) { node* tmp = &(pool[pLast++]); tmp->back = data[pos]; tmp->next = data[pos]->next; if(tmp->next) tmp->next->back = tmp; tmp->id = id; data[pos]->next = tmp; } void append(int L, int R, int id) { ileft[id] = pLast; L += SZ; R += SZ; while(L != R){ if(L&1) append(L++, id); if(R&1) append(--R, id); L >>= 1; R >>= 1; } iright[id] = pLast; } void remove(node* N) { N->back->next = N->next; if(N->next) N->next->back = N->back; } void remove_all(int id) { for(int i=ileft[id]; i<iright[id]; i++) remove(&(pool[i])); ileft[id] = iright[id] = -1; } void each_remove(int pos, int* ret) { int rp = 0; pos += SZ; while(pos){ for(node* nd=data[pos]->next; nd!=NULL; nd=nd->next){ ret[rp++] = nd->id; remove_all(nd->id); remove_all(nd->id ^ 1); //complement } pos >>= 1; } ret[rp++] = -1; } }; struct seg_tree { static const int DEPTH=19, SZ=1<<DEPTH; int val[2*SZ], mx[2*SZ], azero[2*SZ]; seg_tree() { for(int i=0;i<2*SZ;i++){ val[i] = -1; mx[i] = 0; azero[i] = 0; } } void maximize(int pL, int pR, int qL, int qR, int v, int depth) { if((pR<<depth) <= qL || qR <= (pL<<depth)) return; if(qL <= (pL<<depth) && (pR<<depth) <= qR){ val[pL] = max(val[pL], v); if((1<<depth) > azero[pL]) mx[pL] = max(val[pL], max(mx[pL*2], mx[pL*2+1])); else mx[pL] = -1; return; } maximize(pL*2, pL+pR, qL, qR, v, depth-1); maximize(pL+pR, pR*2, qL, qR, v, depth-1); mx[pL] = max(val[pL], max(mx[pL*2], mx[pL*2+1])); } void maximize(int qL, int qR, int v) { maximize(1, 2, qL+SZ, qR+SZ, v, DEPTH); } void zero_set(int p) { p += SZ; for(int i=0;p;i++){ azero[p]++; if(val[p]!=-1){ if((1<<i) <= azero[p]) mx[p] = -1; else mx[p] = max(max(mx[p*2], mx[p*2+1]), val[p]); }else{ mx[p] = max(mx[p*2], mx[p*2+1]); } p >>= 1; } } pair<int, int> best_point() { int pos=1, mv=0, i=DEPTH; while(pos < SZ){ if((1<<(i-1)) <= azero[pos*2]) pos = pos*2 + 1; else if((1<<(i-1)) <= azero[pos*2+1]) pos = pos*2; else if(max(mv, mx[pos*2]) < max(mv, mx[pos*2+1])){ pos = pos*2 + 1; }else{ pos = pos*2; } mv = max(mv, val[pos]); --i; } return make_pair(pos-SZ, mv); } }; struct group { int L1, R1, L2, R2, T; group(){ } group(int l1, int r1, int l2, int r2, int t) { L1 = l1; R1 = r1; L2 = l2; R2 = r2; T = t; } }; int A, B, C, N; int pos[4*MAX], pLast=0; group G[MAX]; int weight[4*MAX]; range_tree range; seg_tree seg; int iTable[2*MAX+1]; void invite(int pos) { range.each_remove(pos, iTable); for(int i=0;iTable[i]>=0;i++){ int ps = iTable[i] / 2; seg.maximize(G[ps].L1, G[ps].R1, G[ps].T); seg.maximize(G[ps].L2, G[ps].R2, G[ps].T); } } int main() { int p, q, r, s, t; scanf("%d%d%d%d", &A, &B, &C, &N); --C; for(int i=0;i<N;i++){ scanf("%d%d%d%d%d", &p, &q, &r, &s, &t); --p; --r; r += A; s += A; pos[pLast++] = p; pos[pLast++] = q; pos[pLast++] = r; pos[pLast++] = s; G[i] = group(p, q, r, s, t); } B += A; sort(pos, pos+pLast); pLast = unique(pos, pos+pLast) - pos; for(int i=0;i<pLast-1;i++){ weight[i] = pos[i+1] - pos[i]; if(pos[i]<=C && C<pos[i+1]){ C = i; --weight[i]; } } for(int i=0;i<N;i++){ G[i].L1 = lower_bound(pos, pos+pLast, G[i].L1) - pos; G[i].L2 = lower_bound(pos, pos+pLast, G[i].L2) - pos; G[i].R1 = lower_bound(pos, pos+pLast, G[i].R1) - pos; G[i].R2 = lower_bound(pos, pos+pLast, G[i].R2) - pos; range.append(G[i].L1, G[i].R1, i*2); range.append(G[i].L2, G[i].R2, i*2+1); } invite(C); if(weight[C]==0) seg.zero_set(C); i64 ret = 0; int count = B - 1; pair<int, int> bLast = make_pair(-1, -1); while(count){ pair<int, int> bp = seg.best_point(); //printf("%d: %d\n", bp.first, bp.second); if(bp.second <= 0){ puts("-1"); return 0; } if(bLast == bp){ //use all; ret += (i64)weight[bp.first] * bp.second; count -= weight[bp.first]; weight[bp.first] = 0; seg.zero_set(bp.first); continue; } ret += bp.second; --count; invite(bp.first); if(--weight[bp.first]==0){ seg.zero_set(bp.first); } bLast = bp; } printf("%lld\n", ret); return 0; }