# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1189403 | simona1230 | Teams (IOI15_teams) | C++20 | 0 ms | 0 KiB |
#include "teams.h"
#include <bits/stdc++.h>
//#include <stdio.h>
//#include <stdlib.h>
using namespace std;
const int maxn=500005;
//static FILE *_inputFile, *_outputFile;
struct node
{
int x,l,r;
node(){}
node(int _x,int _l,int _r)
{
x=_x;
l=_l;
r=_r;
}
};
struct st
{
vector<node> t={{0,-1,-1}};
st(){}
void add_l(int i)
{
if(t[i].l!=-1)return;
t[i].l=t.size();
t.push_back({0,-1,-1});
}
void add_r(int i)
{
if(t[i].r!=-1)return;
t[i].r=t.size();
t.push_back({0,-1,-1});
}
void update(int i,int l,int r,int id)
{
if(l==r)
{
t[i].x+=1;
return;
}
int m=(l+r)/2;
if(id<=m)
{
add_l(i);
update(t[i].l,l,m,id);
}
else
{
add_r(i);
update(t[i].r,m+1,r,id);
}
t[i].x=0;
if(t[i].l!=-1)t[i].x+=t[t[i].l].x;
if(t[i].r!=-1)t[i].x+=t[t[i].r].x;
}
int query(int i,int l,int r,int ql,int qr)
{
if(i==-1||ql>qr)return 0;
if(ql<=l&&r<=qr)return t[i].x;
int m=(l+r)/2;
return query(t[i].l,l,m,ql,min(qr,m))+query(t[i].r,m+1,r,max(m+1,ql),qr);
}
};
struct node2
{
st x;
int l,r;
node2(){}
node2(st _x,int _l,int _r)
{
x=_x;
l=_l;
r=_r;
}
};
st h;
struct s2d
{
vector<node2> t={{h,-1,-1}};
s2d(){}
void add_l(int i)
{
if(t[i].l!=-1)return;
t[i].l=t.size();
t.push_back({h,-1,-1});
}
void add_r(int i)
{
if(t[i].r!=-1)return;
t[i].r=t.size();
t.push_back({h,-1,-1});
}
void update(int i,int l,int r,int i1,int i2)
{
if(l==r)
{
t[i].x.update(0,1,maxn,i2);
return;
}
int m=(l+r)/2;
if(i1<=m)
{
add_l(i);
update(t[i].l,l,m,i1,i2);
}
else
{
add_r(i);
update(t[i].r,m+1,r,i1,i2);
}
if(t[i].l==-1)t[i].x=t[t[i].r].x;
else if(t[i].r==-1)t[i].x=t[t[i].l].x;
else t[i].x.update(0,1,maxn,i2);
}
int query(int i,int l,int r,int l1,int r1,int l2,int r2)
{
if(i==-1||l1>r1)return 0;
if(l1<=l&&r<=r1)return t[i].x.query(0,1,maxn,l2,r2);
int m=(l+r)/2;
return query(t[i].l,l,m,l1,min(r1,m),l2,r2)+query(t[i].r,m+1,r,max(m+1,l1),r1,l2,r2);
}
};
s2d t;
int n;
void init(int N, int A[], int B[])
{
n=N;
for(int i=0;i<N;i++)
t.update(0,1,maxn,A[i],B[i]);
fprintf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}
int dp[maxn];
int can(int M, int k[])
{
int answer=0;
stack<pair<int,int> > s;
for(int i=0;i<M;i++)
{
while(s.size()&&s.top().second==i)s.pop();
int v1=t.query(0,1,maxn,1,k[i],k[i],maxn)-1;
//fprintf(_outputFile,"%d ", v1);
if(s.size()==0/*||dp[s.top().first]>=v1*/)
{
dp[i]=v1;
while(s.size())s.pop();
s.push({i,M});
answer=min(answer,dp[i]);
continue;
}
int j=s.top().first;
dp[i]=dp[j]+t.query(0,1,maxn,k[j]+1,k[i],k[i],maxn)-1;
int ans=M;
int l=i+1,r=M-1;
while(l<=r)
{
int m=(l+r)/2;
if(dp[i]+t.query(0,1,maxn,k[i]+1,k[m],k[m],maxn)>=dp[j]+t.query(0,1,maxn,k[j]+1,k[m],k[m],maxn))
{
ans=m;
r=m-1;
}
else l=m+1;
}
answer=min(answer,dp[i]);
s.push({i,ans});
}
/*for(int i=0;i<M;i++)
{
fprintf(_outputFile,"%d ", dp[i]);
}*/
if(answer<0)return 0;
return 1;
}
/*
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
t.update(0,1,maxn,x,y);
}
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
int x,y,xx,yy;
cin>>x>>y>>xx>>yy;
cout<<t.query(0,1,maxn,x,y,xx,yy)<<endl;
}
return 0;
}
*/