# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
93529 |
2019-01-09T11:28:20 Z |
Bodo171 |
Wall (IOI14_wall) |
C++14 |
|
3000 ms |
14072 KB |
#include "wall.h"
#include <iostream>
#include <climits>
#include <set>
using namespace std;
const int nmax=2*1000*1000+5;
struct aint
{
int mn,mx,whmn,whmx;
}arb[4*nmax],ans;
void mrg(aint &A,aint B,aint C)
{
A=B;
if(C.mn<A.mn) A.mn=C.mn,A.whmn=C.whmn;
if(C.mx>A.mx) A.mx=C.mx,A.whmx=C.whmx;
}
set<int> s;
set<int>::iterator it,it1;
int v[nmax];
int n,poz,i;
void upd(int nod,int l,int r,int poz)
{
if(l==r)
{
arb[nod].mx=arb[nod].mn=v[poz];
arb[nod].whmx=arb[nod].whmn=poz;
if(v[poz]==-1)
{
arb[nod].mx=-1;arb[nod].mn=INT_MAX;
}
return;
}
int m=(l+r)/2;
if(poz<=m) upd(2*nod,l,m,poz);
else upd(2*nod+1,m+1,r,poz);
mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
if(l==r)
{
mrg(ans,ans,arb[nod]);
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m,st,dr);
if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int getmx(int st,int dr)
{
ans.mx=-1,ans.mn=INT_MAX;
query(1,1,n,st,dr);
poz=ans.whmx;
return ans.mx;
}
int getmn(int st,int dr)
{
ans.mx=-1,ans.mn=INT_MAX;
query(1,1,n,st,dr);
poz=ans.whmn;
return ans.mn;
}
void rs(int wh,int llim,int H)
{
it=s.lower_bound(wh);
if(it!=s.begin())
{
it--;
if((*it)<llim-1)
{
v[llim-1]=v[wh];
s.insert(llim-1);
upd(1,1,n,llim-1);
}
}
else
{
if(llim-1)
{
v[llim-1]=v[wh];
s.insert(llim-1);
upd(1,1,n,llim-1);
}
}
s.insert(wh);
v[wh]=H;
upd(1,1,n,wh);
}
void comp(int poz)
{
it=s.lower_bound(poz);
bool brk=0;
if(it!=s.begin())
{
it--;
while(it!=s.begin()&&(!brk))
{
if(v[(*it)]!=v[poz]) brk=1;
else
{
v[(*it)]=-1;
upd(1,1,n,(*it));
it1=it;
it1--;
s.erase(it);
it=it1;
}
}
}
if(s.upper_bound(poz)!=s.end()&&v[(*s.upper_bound(poz))]==v[poz])
{
v[poz]=-1;upd(1,1,n,poz);
s.erase(poz);
}
}
bool finds(int x)
{
return (s.find(x)!=s.end());
}
void build(int nod,int l,int r)
{
if(l==r)
{
arb[nod].whmx=arb[nod].whmn=l;
arb[nod].mx=-1;arb[nod].mn=INT_MAX;
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N;
build(1,1,n);
int h,pp;
s.insert(n);
v[n]=0;
upd(1,1,n,n);
for(int i=0;i<k;i++)
{
left[i]++;right[i]++;
h=height[i];
if(op[i]==1)
{
while(getmn(left[i],right[i])<h)
{
if(finds(poz))
{
rs(poz,left[i],h);
if(finds(left[i]-1))comp(left[i]-1);
if(finds(poz)) comp(poz);
}
}
pp=(*s.lower_bound(right[i]));
if(getmn(pp,pp)<h)
{
if(finds(pp))
{
rs(pp,left[i],v[pp]);
rs(right[i],left[i],h);
if(finds(left[i]-1))comp(left[i]-1);
if(finds(right[i])) comp(right[i]);
}
}
}
else
{
while(getmx(left[i],right[i])>h)
{
rs(poz,left[i],h);
}
pp=(*s.lower_bound(right[i]));
if(getmx(pp,pp)>h)
{
rs(pp,left[i],v[pp]);
rs(right[i],left[i],h);
upd(1,1,n,right[i]);
if(finds(left[i]-1))comp(left[i]-1);
if(finds(right[i])) comp(right[i]);
}
}
}
for(i=1;i<=n;i++)
if(finds(i)) finalHeight[i-1]=v[i];
for(i=n-1;i>=0;i--)
if(!finds(i+1))
finalHeight[i]=finalHeight[i+1];
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
8 ms |
376 KB |
Output is correct |
4 |
Correct |
322 ms |
1144 KB |
Output is correct |
5 |
Correct |
138 ms |
1400 KB |
Output is correct |
6 |
Correct |
137 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
146 ms |
14004 KB |
Output is correct |
3 |
Execution timed out |
3046 ms |
8552 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
8 ms |
504 KB |
Output is correct |
4 |
Correct |
320 ms |
1156 KB |
Output is correct |
5 |
Correct |
135 ms |
1272 KB |
Output is correct |
6 |
Correct |
136 ms |
1400 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
145 ms |
14072 KB |
Output is correct |
9 |
Execution timed out |
3045 ms |
8552 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
9 ms |
376 KB |
Output is correct |
4 |
Correct |
317 ms |
1144 KB |
Output is correct |
5 |
Correct |
136 ms |
1648 KB |
Output is correct |
6 |
Correct |
136 ms |
1408 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
147 ms |
13960 KB |
Output is correct |
9 |
Execution timed out |
3060 ms |
8596 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |