#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#pragma GCC optimize("O3,unroll-loops")
#pragma gcc target ("avx2")
using namespace std;
struct ura
{
int a,b;
};
vector<ura>vec;
const int nmax=1000000;
int aint[1048576*2+10];
int aint2[1048576*2+10];
int inf=1e9+5;
int inter(int i,int j)
{
return max(0,min(vec[i].b,vec[j].b)-max(vec[i].a,vec[j].a));
}
int reun(int i,int j)
{
return max(vec[i].b,vec[j].b)-min(vec[i].a,vec[j].a);
}
int distsol,cost;
multiset<int>lfend;
multiset<int>rgend;
/// qr1 pe partea dreapta
struct undos
{
int unde,pozupdate,delacat;
};
vector<undos>oper;
int qr1(int node,int st,int dr,int qst,int qdr)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
return inf;
if(qst<=st && dr<=qdr)
return aint[node];
int mij=(st+dr)>>1;
return min(qr1(node*2,st,mij,qst,qdr),qr1(node*2+1,mij+1,dr,qst,qdr));
}
int qr2(int node,int st,int dr,int qst,int qdr)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
return -inf;
if(qst<=st && dr<=qdr)
return aint2[node];
int mij=(st+dr)>>1;
return max(qr2(node*2,st,mij,qst,qdr),qr2(node*2+1,mij+1,dr,qst,qdr));
}
void update1(int node,int st,int dr,int poz,int val,int smech)
{
if(st>poz || poz>dr)
return ;
if(poz<=st && dr<=poz)
{
if(smech==1)
aint[node]=val;
else
{
oper.push_back({1,poz,aint[node]});
aint[node]=min(aint[node],val);
}
return;
}
int mij=(st+dr)>>1;
update1(node*2,st,mij,poz,val,smech);
update1(node*2+1,mij+1,dr,poz,val,smech);
aint[node]=min(aint[node*2],aint[node*2+1]);
}
void update2(int node,int st,int dr,int poz,int val,int smech)
{
if(st>poz || poz>dr)
return ;
if(poz<=st && dr<=poz)
{
if(smech==1)
aint2[node]=val;
else
{
oper.push_back({2,poz,aint2[node]});
aint2[node]=max(aint2[node],val);
}
return;
}
int mij=(st+dr)>>1;
update2(node*2,st,mij,poz,val,smech);
update2(node*2+1,mij+1,dr,poz,val,smech);
aint2[node]=max(aint2[node*2],aint2[node*2+1]);
}
void clr(int node,int st,int dr)
{
aint2[node]=-inf;
aint[node]=inf;
if(st!=dr)
{
int mij=(st+dr)/2;
clr(node*2,st,mij);
clr(node*2+1,mij+1,dr);
}
}
multiset<pair<int,int> >solutii;
void undo()
{
undos a;
a=oper.back();
if(a.unde==1)
update1(1,1,nmax,a.pozupdate,a.delacat,1);
else if(a.unde==2)
update2(1,1,nmax,a.pozupdate,a.delacat,1);
else if(a.unde==3)
solutii.erase(solutii.find({a.pozupdate,a.delacat}));
else if(a.unde==4)
rgend.erase(rgend.find(a.pozupdate));
else
lfend.erase(lfend.find(a.pozupdate));
oper.pop_back();
}
void add(ura x)
{
int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
if(lfend.size() && x.b>*prev(lfend.end()))
{
supra=x.b-*prev(lfend.end());
nosupra=qr1(1,1,nmax,*prev(lfend.end()),nmax)-x.a;
}
else if(lfend.size())
{
supra=0;
nosupra=qr1(1,1,nmax,x.b,nmax)-x.a;
}
lfend.insert(x.a);
update1(1,1,nmax,x.a,x.b,0);
if(rgend.size() && x.a<=*rgend.begin())
{
supra1=*rgend.begin()-x.a;
nosupra1=x.b-qr2(1,1,nmax,1,*rgend.begin());
}
else if(rgend.size())
{
supra1=0;
nosupra1=x.b-qr2(1,1,nmax,1,x.a);
}
rgend.insert(x.b);
update2(1,1,nmax,x.b,x.a,0);
if(supra1<supra)
{
swap(supra1,supra);
swap(nosupra1,nosupra);
}
else if(supra1==supra)
{
nosupra=min(nosupra1,nosupra);
}
if(supra>=x.b-x.a)
{
supra=x.b-x.a;
nosupra=x.b-x.a;
}
solutii.insert({supra,nosupra});
oper.push_back({3,supra,nosupra});
oper.push_back({4,x.b,0});
oper.push_back({5,x.a,0});
}
vector<ura>vectorus[1048576+100];
unordered_map<long long,int>fre;
unordered_map<long long,int>lst;
void dncadd(int node,int st,int dr,int qst,int qdr,int lf,int rg)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return ;
}
if(qst<=st && dr<=qdr)
{
vectorus[node].push_back({lf,rg});
return;
}
int mij=(st+dr)/2;
dncadd(node*2,st,mij,qst,qdr,lf,rg);
dncadd(node*2+1,mij+1,dr,qst,qdr,lf,rg);
}
void dfsdnc(int curr,int st,int dr)
{
int number=oper.size();
for(int j=0;j<vectorus[curr].size();j++)
{
add(vectorus[curr][j]);
}
if(st==dr)
{
cout<<solutii.begin()->second<<'\n';
}
else
{
int mij=(st+dr)/2;
dfsdnc(curr*2,st,mij);
dfsdnc(curr*2+1,mij+1,dr);
}
while(oper.size()>number)
{
undo();
}
}
long long hs(int a,int b)
{
return a*nmax+b;
}
int main()
{
int n,i,j,k,l,r,z;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
char tip;
for(i=1; i<=n; i++)
{
cin>>tip;
if(tip=='A')
{
cin>>l>>r;
l++;
r++;
fre[hs(l,r)]++;
if(fre[hs(l,r)]==1)
lst[hs(l,r)]=i;
}
else if(tip=='R')
{
cin>>l>>r;
l++;
r++;
fre[hs(l,r)]--;
if(fre[hs(l,r)]==0)
{
dncadd(1,1,n,lst[hs(l,r)],i-1,l,r);
}
}
}
for(auto j :fre)
{
if(j.second>0)
{
dncadd(1,1,n,lst[j.first],n,j.first/nmax,j.first%nmax);
}
}
clr(1,1,nmax);
dfsdnc(1,1,n);
return 0;
}
Compilation message
Main.cpp:7: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
7 | #pragma gcc target ("avx2")
|
Main.cpp: In function 'void add(ura)':
Main.cpp:123:9: warning: unused variable 'sol' [-Wunused-variable]
123 | int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
| ^~~
Main.cpp:123:17: warning: unused variable 'cost' [-Wunused-variable]
123 | int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
| ^~~~
Main.cpp: In function 'void dfsdnc(int, int, int)':
Main.cpp:188:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(int j=0;j<vectorus[curr].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:202:22: warning: comparison of integer expressions of different signedness: 'std::vector<undos>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
202 | while(oper.size()>number)
| ~~~~~~~~~~~^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:213:13: warning: unused variable 'j' [-Wunused-variable]
213 | int n,i,j,k,l,r,z;
| ^
Main.cpp:213:15: warning: unused variable 'k' [-Wunused-variable]
213 | int n,i,j,k,l,r,z;
| ^
Main.cpp:213:21: warning: unused variable 'z' [-Wunused-variable]
213 | int n,i,j,k,l,r,z;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
41564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
41564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
41564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3436 ms |
119392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
41564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
