Submission #606496

#TimeUsernameProblemLanguageResultExecution timeMemory
606496cheissmartTeams (IOI15_teams)C++14
Compilation error
0 ms0 KiB
#include "teams.h" #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7, N = 5e5 + 7; int n; int l[N], r[N]; vi p, ev[N]; namespace pseg { const int MX = 6e8; int h[N], sz = 1; int tree[MX][3]; void pull(int u) { tree[u][2] = tree[tree[u][0]][2] + tree[tree[u][1]][2]; } int upd(int t, int pos, int tl = 0, int tr = n) { if(tr - tl == 1) { tree[sz][2] = 1; return sz++; } int u = sz++; tree[u][0] = tree[t][0], tree[u][1] = tree[t][1]; int tm = (tl + tr) / 2; if(pos < tm) tree[u][0] = upd(tree[t][0], pos, tl, tm); else tree[u][1] = upd(tree[t][1], pos, tm, tr); pull(u); return u; } int qry(int t1, int t2, int ql, int qr, int tl = 0, int tr = n) { if(!t1 && !t2) return 0; if(ql <= tl && tr <= qr) return tree[t2][2] - tree[t1][2]; int tm = (tl + tr) / 2; int ans = 0; if(ql < tm) ans += qry(tree[t1][0], tree[t2][0], ql, qr, tl, tm); if(qr > tm) ans += qry(tree[t1][1], tree[t2][1], ql, qr, tm, tr); return ans; } int find_who(int t1, int t2, int need) { int tl = 0, tr = n; while(tr - tl > 1) { int tm = (tl + tr) / 2; if(tree[tree[t2][0]][2] - tree[tree[t1][0]][2] > need) t1 = tree[t1][0], t2 = tree[t2][0], tr = tm; else need -= (tree[tree[t2][0]][2] - tree[tree[t1][0]][2]), t1 = tree[t1][1], t2 = tree[t2][1], tl = tm; } return tl; } } void init(int _n, int _l[], int _r[]) { n = _n; for(int i = 0; i < n; i++) l[i] = _l[i], r[i] = _r[i]; p = vi(n); iota(ALL(p), 0); sort(ALL(p), [&] (int x, int y) { return r[x] < r[y]; }); for(int i = 0; i < n; i++) ev[l[p[i]]].PB(i); for(int i = 1; i <= n; i++) { pseg::h[i] = pseg::h[i - 1]; for(int j:ev[i]) pseg::h[i] = pseg::upd(pseg::h[i], j); } } struct seg { int r, hi; }; int can(int m, int a[]) { if(accumulate(a, a + m, 0LL) > n) return 0; sort(a, a + m); V<seg> stk; stk.PB({0, n}); for(int i = 0, j = 0; i < m; i++) { int need = 0, ii = i; while(i < m && a[i] == a[ii]) need += a[i++]; i--; while(j < n && r[p[j]] < a[i]) j++; while(stk.back().hi < j) { assert(SZ(stk)); stk.pop_back(); } int at_least = j; while(need && SZ(stk)) { int lb = stk.back().r, rb = a[i]; // (lb, rb] int cnt = pseg::qry(pseg::h[lb], pseg::h[rb], at_least, stk.back().hi); if(cnt < need) { at_least = stk.back().hi; stk.pop_back(); need -= cnt; } else if(cnt == need) { at_least = stk.back().hi; stk.pop_back(); stk.PB({a[i], at_least}); need -= cnt; break; } else { int dead = pseg::qry(pseg::h[lb], pseg::h[rb], 0, at_least); int who = pseg::find_who(pseg::h[lb], pseg::h[rb], need + dead); stk.PB({a[i], who}); break; } } if(stk.empty()) return 0; } return 1; }

Compilation message (stderr)

/tmp/ccMFlKGg.o: in function `__tcf_0':
teams.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `ev' defined in .bss section in /tmp/ccMFlKGg.o
/tmp/ccMFlKGg.o: in function `void std::__adjust_heap<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, long, int, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, long, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}>) [clone .constprop.0]':
teams.cpp:(.text+0x7e): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMFlKGg.o
teams.cpp:(.text+0xfb): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMFlKGg.o
/tmp/ccMFlKGg.o: in function `void std::__insertion_sort<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}>, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}>) [clone .constprop.0]':
teams.cpp:(.text+0x1d9): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMFlKGg.o
/tmp/ccMFlKGg.o: in function `void std::__introsort_loop<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, long, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}> >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}>, long, __gnu_cxx::__ops::_Iter_comp_iter<init(int, int*, int*)::{lambda(int, int)#1}>)':
teams.cpp:(.text+0x3ca): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMFlKGg.o
/tmp/ccMFlKGg.o: in function `pseg::find_who(int, int, int)':
teams.cpp:(.text+0x1447): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccMFlKGg.o
/tmp/ccMFlKGg.o: in function `init(int, int*, int*)':
teams.cpp:(.text+0x1517): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccMFlKGg.o
teams.cpp:(.text+0x1526): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMFlKGg.o
teams.cpp:(.text+0x1534): relocation truncated to fit: R_X86_64_PC32 against symbol `l' defined in .bss section in /tmp/ccMFlKGg.o
teams.cpp:(.text+0x1640): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/ccMFlKGg.o
teams.cpp:(.text+0x1651): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status