Submission #1085458

#TimeUsernameProblemLanguageResultExecution timeMemory
1085458yeediotTeams (IOI15_teams)C++17
0 / 100
308 ms141696 KiB
#include<bits/stdc++.h> #include "teams.h" using namespace std; #define ll long long #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define __lg(x) 63-__builtin_clzll(x) #define pow2(x) (1LL<<x) const int mxn = 5e5 + 5; int cnt, rt[mxn]; struct segtree{ struct nde{ int l, r, c; }seg[mxn << 5]; #define x seg[node] int build(int l, int r){ int node = ++cnt; seg[node].c = 0; if(l == r){ return node; } int mm = l + r >> 1; x.l = build(l, mm), x.r = build(mm + 1, r); return node; } int ins(int from, int l, int r, int p){ int node = ++cnt; seg[node] = seg[from]; seg[node].c++; if(l == r){ return node; } int mm = l + r >> 1; if(p <= mm){ x.l = ins(x.l, l, mm, p); } else{ x.r = ins(x.r, mm + 1, r, p); } //x.c = seg[x.l].c + seg[x.r].c; return node; } int kth(int v, int u, int l, int r, int k){ if(l == r){ return l; } int mm = l + r >> 1; int cc = seg[seg[v].r].c - seg[seg[u].r].c; if(k > cc){ return kth(seg[v].l, seg[u].l, l, mm, k - cc); } else{ return kth(seg[v].r, seg[u].r, mm + 1, r, k); } } int bs(int v, int u, int l, int r, int k){ if(l == r){ return seg[v].c - seg[u].c; } int mm = l + r >> 1; if(k > mm){ return bs(seg[v].r, seg[u].r, mm + 1, r, k); } else{ return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c; } } }tr; int n; void init(int N, int a[], int b[]){ n = N; rt[0] = tr.build(1, n); vector<pii>pt; for(int i = 0; i < n; i++){ pt.pb({a[i], b[i]}); } sort(all(pt)); int pos = 0; for(int i = 1; i <= n; i++){ rt[i] = rt[i - 1]; for(; pos < n and pt[pos].F == i; pos++){ tr.ins(rt[i], 1, n, pt[pos].S); } } } int can(int m, int K[]){ vector<array<int, 3>>st; vector<int>k; for(int i = 0; i < m; i++) k.pb(K[i]); st.pb({0, 0, 0}); sort(all(k)); for(auto i : k){ while(sz(st) > 1 and st.back()[1] < i){ st.pop_back(); } int tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i; if(tot < 0){ return 0; } int cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]); while(sz(st) > 1 and cur > st.back()[1]){ st.pop_back(); cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]); } st.pb({i, cur, tot}); } return 1; }

Compilation message (stderr)

teams.cpp: In member function 'int segtree::build(int, int)':
teams.cpp:32:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::ins(int, int, int, int)':
teams.cpp:43:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::kth(int, int, int, int, int)':
teams.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::bs(int, int, int, int, int)':
teams.cpp:70:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mm = l + r >> 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...