제출 #51846

#제출 시각아이디문제언어결과실행 시간메모리
51846radoslav11팀들 (IOI15_teams)C++14
100 / 100
2160 ms538808 KiB
#include <bits/stdc++.h> //#include "Lgrader.cpp" #define endl '\n' using namespace std; template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; } template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; } const int MAXN = (int)5e5 + 42; struct node { int sz; node *l, *r; node() { sz = 0; l = r = nullptr; } node(int val) { sz = val; l = r = nullptr; } void pushup() { sz = 0; if(l) sz += l->sz; if(r) sz += r->sz; } }; using pnode = node*; bool keep; /* list<pnode> keep_for_erase; pnode new_node(int sz = 0) { auto it = new node(sz); if(keep) keep_for_erase.push_back(it); return it; }*/ pnode ptr_list[MAXN * 10]; int psz = 0; pnode new_node(int sz = 0) { if(!keep) return new node(sz); if(!ptr_list[psz]) ptr_list[psz] = new node(); ptr_list[psz]->l = ptr_list[psz]->r = nullptr; ptr_list[psz]->sz = sz; return ptr_list[psz++]; } inline int size(pnode it) { return it ? it->sz : 0; } pnode build_tree(int l, int r) { if(l == r) return new_node(0); int mid = (l + r) >> 1; pnode ret = new_node(); ret->l = build_tree(l, mid); ret->r = build_tree(mid + 1, r); ret->pushup(); return ret; } pnode remove_less(int pos, int l, int r, pnode tmp) { if(!tmp) return nullptr; if(l == r) return nullptr; int mid = (l + r) >> 1; pnode ret = new_node(); if(mid < pos) { ret->l = nullptr; ret->r = remove_less(pos, mid + 1, r, tmp ? tmp->r : nullptr); } else { ret->l = remove_less(pos, l, mid, tmp ? tmp->l : nullptr); ret->r = tmp ? tmp->r : nullptr; } ret->pushup(); return ret; } pnode add_val(int pos, int l, int r, pnode tmp) { if(pos < l) return tmp; if(pos > r) return tmp; if(l == r) return new_node(size(tmp) + 1); int mid = (l + r) >> 1; pnode ret = new node(); ret->l = add_val(pos, l, mid, tmp ? tmp->l : nullptr); ret->r = add_val(pos, mid + 1, r, tmp ? tmp->r : nullptr); ret->pushup(); return ret; } int n; vector<int> li[MAXN]; pnode root[MAXN]; void init(int n, int a[], int b[]) { ::n = n; root[0] = nullptr; for(int i = 1; i <= n; i++) li[i].clear(); for(int i = 0; i < n; i++) li[a[i]].push_back(b[i]); pnode last = root[0]; for(int i = 1; i <= n; i++) { root[i] = last; for(int x: li[i]) root[i] = last = add_val(x, 1, n, last); //if(i != 1) root[i] = last = remove_less(i - 1, 1, n, last); } } pnode used; int size_diff_l(pnode used, pnode actual) { int sz = actual ? size(actual->l) : 0; if(used) sz -= size(used->l); return sz; } int Kth_val; inline pnode L(pnode it) { return it ? it->l : nullptr; } inline pnode R(pnode it) { return it ? it->r : nullptr; } pnode get_new_used(int start, int l, int r, pnode used, pnode tmp) { if(size(tmp) - size(used) <= 0) return used; if(r < start) return nullptr; if(Kth_val == 0) return used; if(l == r) { int q = min(Kth_val, size(tmp) - size(used)); Kth_val -= q; return new_node(size(used) + q); } int mid = (l + r) >> 1; pnode ret = new_node(); if(start <= l) { if(size(tmp) - size(used) <= Kth_val) { Kth_val -= size(tmp) - size(used); return tmp; } if(size_diff_l(used, tmp) >= Kth_val) { ret->l = get_new_used(start, l, mid, L(used), L(tmp)); ret->r = R(used); } else { ret->l = L(tmp); Kth_val -= size_diff_l(used, tmp); ret->r = get_new_used(start, mid + 1, r, R(used), R(tmp)); } } else { ret->l = get_new_used(start, l, mid, L(used), L(tmp)); if(Kth_val) ret->r = get_new_used(start, mid + 1, r, R(used), R(tmp)); else ret->r = R(used); } ret->pushup(); return ret; } int can(int m, int k[]) { int sum = 0; for(int i = 0; i < m; i++) { sum += k[i]; if(sum > n) return 0; } int actual_psz = psz; used = nullptr; keep = 1; sort(k, k + m); for(int i = 0; i < m; i++) { int K = k[i]; //if(K != 1) used = remove_less(K - 1, 1, n, used); Kth_val = K; used = get_new_used(K, 1, n, used, root[K]); if(Kth_val) { keep = 0; psz = actual_psz; return 0; } } keep = 0; /* while(!keep_for_erase.empty()) { auto it = keep_for_erase.back(); keep_for_erase.pop_back(); free(it); //delete it; }*/ //while(psz > actual_psz) free(ptr_list[--psz]); psz = actual_psz; return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:113:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void init(int n, int a[], int b[])
                                  ^
teams.cpp:109:5: note: shadowed declaration is here
 int n;
     ^
teams.cpp: In function 'int size_diff_l(pnode, pnode)':
teams.cpp:135:41: warning: declaration of 'used' shadows a global declaration [-Wshadow]
 int size_diff_l(pnode used, pnode actual)
                                         ^
teams.cpp:133:7: note: shadowed declaration is here
 pnode used;
       ^~~~
teams.cpp: In function 'node* get_new_used(int, int, int, pnode, pnode)':
teams.cpp:147:66: warning: declaration of 'used' shadows a global declaration [-Wshadow]
 pnode get_new_used(int start, int l, int r, pnode used, pnode tmp)
                                                                  ^
teams.cpp:133:7: note: shadowed declaration is here
 pnode used;
       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...