#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct ura
{
int a,b;
};
vector<ura>vecus[500005];
vector<ura>vec;
const int nmax=10000005;
int aint[nmax*4];
int aint2[nmax*4];
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);
}
long long distsol,cost;
multiset<int>lfend;
multiset<int>rgend;
/// qr1 pe partea dreapta
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)/2;
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)/2;
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)
{
if(st>poz || poz>dr)
{
return ;
}
if(poz<=st && dr<=poz)
{
aint[node]=min(aint[node],val);
return;
}
int mij=(st+dr)/2;
update1(node*2,st,mij,poz,val);
update1(node*2+1,mij+1,dr,poz,val);
aint[node]=min(aint[node*2],aint[node*2+1]);
}
void update2(int node,int st,int dr,int poz,int val)
{
if(st>poz || poz>dr)
{
return ;
}
if(poz<=st && dr<=poz)
{
aint2[node]=max(aint2[node],val);
return;
}
int mij=(st+dr)/2;
update2(node*2,st,mij,poz,val);
update2(node*2+1,mij+1,dr,poz,val);
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 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);
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);
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});
}
int main()
{
int n,i,j,k,l,r,z;
cin>>n;
char tip;
for(i=1;i<=n;i++)
{
cin>>tip;
if(tip=='A')
{
cin>>l>>r;
vec.push_back({l,r});
}
else if(tip=='R')
{
cin>>l>>r;
for(j=0;j<vec.size();j++)
{
if(vec[j].a==l && vec[j].b==r)
{
vec.erase(vec.begin()+j);
break;
}
}
}
for(j=0;j<vec.size();j++)
{
vecus[i].push_back({vec[j]});
}
/*
int minim=1e9,sol;
for(j=0;j<vec.size();j++)
{
for(z=j;z<vec.size();z++)
{
if(inter(z,j)<minim)
{
minim=inter(z,j);
sol=reun(z,j);
}
else if(inter(z,j)==minim)
{
sol=min(sol,reun(z,j));
}
}
}
cout<<sol<<'\n';
*/
}
for(i=1;i<=n;i++)
{
distsol=1e9;
cost=0;
clr(1,1,nmax);
lfend.clear();
rgend.clear();
solutii.clear();
for(j=0;j<vecus[i].size();j++)
{
add(vecus[i][j]);
// cout<<vecus[i][j].a<<" "<<vecus[i][j].b<<'\n';
}
cout<<solutii.begin()->second<<'\n';
// cout<<solve();
}
return 0;
}
Compilation message
Main.cpp: In function 'void add(ura)':
Main.cpp:100:9: warning: unused variable 'sol' [-Wunused-variable]
100 | int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
| ^~~
Main.cpp:100:17: warning: unused variable 'cost' [-Wunused-variable]
100 | int sol=inf,cost=inf,supra=inf,nosupra=inf,supra1=inf,nosupra1=inf;
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(j=0;j<vec.size();j++)
| ~^~~~~~~~~~~
Main.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(j=0;j<vec.size();j++)
| ~^~~~~~~~~~~
Main.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(j=0;j<vecus[i].size();j++)
| ~^~~~~~~~~~~~~~~~
Main.cpp:143:15: warning: unused variable 'k' [-Wunused-variable]
143 | int n,i,j,k,l,r,z;
| ^
Main.cpp:143:21: warning: unused variable 'z' [-Wunused-variable]
143 | int n,i,j,k,l,r,z;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7089 ms |
276216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7089 ms |
276216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7089 ms |
276216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
698 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7089 ms |
276216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
