제출 #584832

#제출 시각아이디문제언어결과실행 시간메모리
584832AngusRitossa팀들 (IOI15_teams)C++14
77 / 100
4054 ms500048 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; struct ptreenode { int left, right, val; // val = num }; ptreenode ptree[20000000]; int upto; void pupdate(int node, int curr, int oldcurr, int cstart = 0, int cend = 500010) { if (cstart == cend) { ptree[curr].val = ptree[oldcurr].val+1; return; } int mid = (cstart+cend)/2; if (node <= mid) { ptree[curr].left = ++upto; ptree[curr].right = ptree[oldcurr].right; pupdate(node, ptree[curr].left, ptree[oldcurr].left, cstart, mid); } else { ptree[curr].right = ++upto; ptree[curr].left = ptree[oldcurr].left; pupdate(node, ptree[curr].right, ptree[oldcurr].right, mid+1, cend); } ptree[curr].val = ptree[ptree[curr].left].val + ptree[ptree[curr].right].val; } int pquery(int s, int e, int curr, int cstart = 0, int cend = 500010) { if (s <= cstart && cend <= e) return ptree[curr].val; int mid = (cstart+cend)/2; if (e <= mid) return pquery(s, e, ptree[curr].left, cstart, mid); else if (s > mid) return pquery(s, e, ptree[curr].right, mid+1, cend); else return pquery(s, e, ptree[curr].left, cstart, mid) + pquery(s, e, ptree[curr].right, mid+1, cend); } struct otreenode { int left, right, val, last, lazy; // val = last in its subtree; }; otreenode otree[20000000]; int upto2, n; int roots[500010]; void push(int curr, int cstart, int mid, int cend) { if (!otree[curr].left) otree[curr].left = ++upto2; if (!otree[curr].right) otree[curr].right = ++upto2; if (!otree[curr].lazy) return; int l = otree[curr].left; int r = otree[curr].right; otree[l].last = otree[r].last = otree[l].lazy = otree[r].lazy = otree[curr].lazy; int a = pquery(cstart, mid, roots[otree[curr].lazy]); int b = pquery(mid+1, cend, roots[otree[curr].lazy]); // printf("%d %d %d a %d b %d\n", cstart, mid, cend, a, b); otree[l].val = a; otree[r].val = b; otree[curr].lazy = 0; } void oupdate(int s, int e, int val, int curr, int cstart = 0, int cend = 500010) { if (s <= cstart && cend <= e) { // printf("updating %d %d %d\n", cstart, cend, val); otree[curr].last = otree[curr].lazy = val; int a = pquery(cstart, cend, roots[val]); otree[curr].val = a; // printf("a %d\n", a); return; } int mid = (cstart+cend)/2; push(curr, cstart, mid, cend); if (e <= mid) oupdate(s, e, val, otree[curr].left, cstart, mid); else if (s > mid) oupdate(s, e, val, otree[curr].right, mid+1, cend); else { oupdate(s, e, val, otree[curr].left, cstart, mid); oupdate(s, e, val, otree[curr].right, mid+1, cend); } otree[curr].val = otree[otree[curr].left].val + otree[otree[curr].right].val; otree[curr].last = otree[otree[curr].right].last; } int treewalkfindfirstbelow(int val, int curr, int cstart = 0, int cend = 500010) { if (cstart == cend) return cstart; int mid = (cstart+cend)/2; push(curr, cstart, mid, cend); if (otree[otree[curr].left].last <= val) return treewalkfindfirstbelow(val, otree[curr].left, cstart, mid); else return treewalkfindfirstbelow(val, otree[curr].right, mid+1, cend); } int ROOT; int othertreewalk(int amreq, int e, int curr, int cstart = 0, int cend = 500010, int amtoside = 0) { if (cstart == cend) { amtoside += otree[curr].val; int hei = otree[curr].last; //printf("%d %d %d - %d %d\n", amreq, e, cstart, pquery(cstart, e, roots[n]), amtoside); if (pquery(cstart, e, roots[n])-amtoside < amreq) { // Impossible // what a shame return 0; } int S = hei; int E = n; while (S != E) { int mid = (S+E)/2; if (pquery(cstart, e, roots[mid])-amtoside < amreq) S = mid+1; else E = mid; } // printf("%d %d %d - %d, %d %d\n", cstart, e, S, amreq, pquery(cstart, e, roots[S]), amtoside); oupdate(cstart, e, S, ROOT); return 1; } int mid = (cstart+cend)/2; push(curr, cstart, mid, cend); // consider last in left subtree int h = otree[otree[curr].left].last; int am = -1; if (mid+1 <= e) am = pquery(mid+1, e, roots[h]) - otree[otree[curr].right].val - amtoside; // printf("%d %d am %d - %d mid+1, e, %d %d - query %d right val %d, amtoside %d\n", cstart, cend, am, h, mid+1, e, am+otree[otree[curr].right].val + amtoside, otree[otree[curr].right].val, amtoside); if (am < amreq) // have to go to left { amtoside += otree[otree[curr].right].val; return othertreewalk(amreq, e, otree[curr].left, cstart, mid, amtoside); } else { return othertreewalk(amreq, e, otree[curr].right, mid+1, cend, amtoside); } } int lastA[500010]; int lastB[500010]; int x[500010], y[500010]; void init(int N, int A[], int B[]) { n = N; fill_n(lastA, 500010, 0); fill_n(lastB, 500010, 0); vector<pair<int, int> > sortedbyA; for (int i = 0; i < n; i++) { sortedbyA.emplace_back(A[i], i); } sort(sortedbyA.begin(), sortedbyA.end()); for (int i = 0; i < n; i++) { if (i == n-1) { for (int j = sortedbyA[i].first; j <= N; j++) lastA[j] = i+1; } else if (sortedbyA[i].first != sortedbyA[i+1].first) { for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++) { lastA[j] = i+1; } } x[sortedbyA[i].second] = i+1; } sortedbyA.clear(); for (int i = 0; i < n; i++) { sortedbyA.emplace_back(B[i], i); } sort(sortedbyA.begin(), sortedbyA.end()); for (int i = 0; i < n; i++) { if (i == n-1) { for (int j = sortedbyA[i].first; j <= N; j++) lastB[j] = i+1; } else if (sortedbyA[i].first != sortedbyA[i+1].first) { for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++) { lastB[j] = i+1; } } y[sortedbyA[i].second] = i+1; } sortedbyA.clear(); for (int i = 0; i < n; i++) { // printf("%d %d\n", x[i], y[i]); sortedbyA.emplace_back(y[i], x[i]); } sort(sortedbyA.begin(), sortedbyA.end()); for (auto a : sortedbyA) { // assert(!roots[a.first]); roots[a.first] = ++upto; // printf("at %d - updating %d\n", a.first, a.second); pupdate(a.second, roots[a.first], roots[a.first-1]); // printf("%d\n", pquery(0, n, roots[a.first])); } } int can(int m, int k[]) { sort(k, k+m); int r = ++upto2; ROOT = r; for (int i = 0; i < m; i++) { int a = lastA[k[i]]; int b = lastB[k[i]-1]; int s = treewalkfindfirstbelow(b, r); // printf("%d\n", s); if (s <= n) oupdate(s, n, b, r); int res = othertreewalk(k[i], a, r); if (!res) return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...