| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1032839 | Dan4Life | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define ub upper_bound
using ar2 = array<int,2>;
const int mxN = (int)5e5+10;
const int mxM = (int)2e5+10;
ar2 v[mxN]; int n;
multiset<int> S;
const int B = sqrt(mxM);
const int mxLg = __lg(mxN)+1;
const int mxSeg = mxN*4*mxLg;
int a[mxN], b[mxN];
int seg[mxSeg], L[mxSeg], R[mxSeg], root[mxSeg];
int segNodes = 1;
struct OffBIT2D {
bool mode = 0;
vector<ar2> todo;
int cnt[mxN], st[mxN];
vector<int> bit, val;
void init() {
assert(!mode); mode = 1;
int lst[mxN];
for(int i = 0; i < mxN; i++) lst[i] = cnt[i] = 0;
sort(all(todo),[&](ar2 a, ar2 b){ return a[1]<b[1]; });
for(auto t : todo)
for(int x = t[0]; x<mxN; x+=x&-x)
if(lst[x]!=t[1]) lst[x]=t[1],cnt[x]++;
int sum = 0;
for(int i = 0; i < mxN; i++)
lst[i] = 0, sum+=cnt[i], st[i]=sum;
val.resize(sum); bit.resize(sum); reverse(all(todo));
for(auto t : todo)
for(int x = t[0]; x<mxN; x+=x&-x)
if(lst[x]!=t[1]) lst[x]=t[1], val[--st[x]]=t[1];
}
int rank(int y, int l, int r) {
return ub(begin(val)+l,begin(val)+r,y)-begin(val)-l;
}
void UPD(int x, int y, int t) {
for (y = rank(y,st[x],st[x]+cnt[x]); y <= cnt[x]; y += y&-y)
bit[st[x]+y-1] += t;
}
void upd(int x, int y, T t) {
if (!mode) todo.pb({x,y});
else for (;x<SZ;x+=x&-x) UPD(x,y,t);
}
int QUERY(int x, int y) {
int s = 0;
for (y = rank(y,st[x],st[x]+cnt[x]); y; y -= y&-y)
s+=bit[st[x]+y-1];
return s;
}
int query(int x, int y) {
assert(mode);
int s = 0; for (;x;x-=x&-x) s += QUERY(x,y);
return s;
}
int query(int xl, int xr, int yl, int yr) {
return query(xr,yr)-query(xl-1,yr)
-query(xr,yl-1)+query(xl-1,yl-1);
}
};
OffBIT2D<int,mxN> fen2d;
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++) a[i]=A[i],b[i]=B[i];
for(int i = 0; i < n; i++) v[i]={a[i],b[i]},fen2d.upd(a[i],b[i],1);
fen2d.init();
sort(v,v+n,[&](ar2 x, ar2 y){ return x[1]>y[1]; });
}
int dp[B+10];
int f(int j, int i, int a[]){
return dp[j]+fen2d.query(a[j]+1,a[i],a[i],n);
}
int can(int m, int a[]) {
sort(a,a+m);
if(m>=B){
reverse(a,a+m);
int j = 0; S.clear();
for(int i = 0; i < m; i++){
int x = a[i];
while(j<n and v[j][1]>=a[i])
S.insert(v[j][0]), j++;
while(x--){
auto itr = S.upper_bound(a[i]);
if(itr==begin(S)) return 0;
S.erase(--itr);
}
}
return 1;
}
deque<int> dq; dq.clear();
for(int i = 0; i < m; i++){
dp[i] = fen2d.query(1,a[i],a[i],n);
while(sz(dq)>1 and f(end(dp)[-2],i,a) < f(end(dp)[-1],i,a)) dq.pop_back();
if(sz(dq)){
//int j = dq.back();
for(auto j : dq) dp[i] = min(dp[i], f(j,i,a));
}
dp[i]-=a[i];
if(dp[i]<0) return 0;
dq.pb(i);
}
return 1;
}