| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171206 |
2019-12-27T18:59:26 Z |
CaroLinda |
Wall (IOI14_wall) |
C++14 |
|
3000 ms |
233188 KB |
#include "wall.h"
#include <bits/stdc++.h>
#define debug
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int, int>
#define mkt make_tuple
const int MAXN = 2e6+10 , inf = 1e9+10 ;
using namespace std ;
struct Seg
{
struct Node
{
int lef , rig, mxLef , mnRig ;
bool locked ;
Node()
{
lef = mxLef =-inf , rig = mnRig = inf ;
locked = false ;
}
} ;
Node tree[MAXN*4] ;
int m(int l, int r) { return (l+r)>>1 ; }
void merge(int pos, int l, int r)
{
tree[pos].mxLef = tree[pos].lef ;
tree[pos].mnRig =tree[pos].rig ;
tree[pos].mxLef = max(tree[pos].mxLef, max( tree[pos*2].mxLef, tree[pos*2+1].mxLef ) ) ;
tree[pos].mnRig = min( tree[pos].mnRig , min(tree[pos*2].mnRig, tree[pos*2+1].mnRig )) ;
}
void check(int pos, int l, int r, int curL, int curR , vector<int> &List )
{
if( tree[pos].locked ) return ;
curL = max( curL, tree[pos].lef ) ;
curR = min( curR, tree[pos].rig ) ;
if( tree[pos].mnRig >= curL && tree[pos].mxLef <= curR )
return ;
if( l == r )
{
List.pb(l) ;
tree[pos].locked = true ;
tree[pos].lef = -inf ;
tree[pos].rig = inf ;
return ;
}
check(pos*2,l,m(l,r), curL, curR , List ) ;
check(pos*2+1,m(l,r)+1, r, curL, curR, List ) ;
if( tree[pos*2].locked && tree[pos*2+1].locked )
{
tree[pos].locked = true ;
tree[pos].lef = -inf ;
tree[pos].rig = inf ;
}
}
void upd(int pos, int l, int r, int beg, int en ,int num, int type, int curL, int curR, vector<int> &v )
{
if( tree[pos].locked || r < beg || l > en ) return ;
curL = max(curL, tree[pos].lef ) ;
curR = min( curR, tree[pos].rig ) ;
if( l >= beg && r <= en )
{
if( type == 1 ) tree[pos].lef = max( tree[pos].lef, num ) ;
else tree[pos].rig = min( tree[pos].rig, num ) ;
merge(pos,l,r) ;
check(pos,l,r,curL,curR, v) ;
return ;
}
upd(pos*2,l,m(l,r),beg, en, num ,type, curL, curR,v) ;
upd(pos*2+1,m(l,r)+1, r, beg, en , num , type , curL, curR,v ) ;
merge(pos,l,r) ;
}
void print(int pos, int l, int r, int curL, int curR)
{
curL = max(curL, tree[pos].lef ) ;
curR = min( curR, tree[pos].rig ) ;
if(l == r) return (void)(printf("%d -> %d %d\n" , l , curL, curR)) ;
print(pos*2,l,m(l,r), curL, curR ) ;
print(pos*2+1,m(l,r)+1, r, curL, curR ) ;
}
} ;
struct secondSeg
{
struct Node
{
int lef, rig ;
Node() { lef = -inf , rig = inf ; }
} ;
Node v[MAXN*4] ;
int m(int l, int r) { return (l+r)>>1 ; }
void upd(int pos, int l, int r, int beg, int en,int num, int type )
{
if( l > en || r < beg ) return ;
if( l >= beg && r <= en )
{
if(type==1) v[pos].lef = max(v[pos].lef, num) ;
else v[pos].rig = min(v[pos].rig, num) ;
return ;
}
upd(pos*2,l,m(l,r),beg,en,num,type) ;
upd(pos*2+1,m(l,r)+1, r, beg, en , num , type ) ;
}
void qry(int pos, int l, int r, int &curL, int &curR , int idx )
{
curL = max(curL, v[pos].lef ) ;
curR = min(curR, v[pos].rig ) ;
if( l == r ) return ;
if( idx <= m(l,r) ) qry(pos*2,l,m(l,r), curL, curR , idx ) ;
else qry(pos*2+1, m(l,r)+1, r, curL, curR , idx ) ;
}
} ;
int scramble[MAXN] , idx[MAXN] ;
Seg seg ;
secondSeg seg2 ;
bool cmp(int i, int j) { return scramble[i] < scramble[j] ; }
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
reverse(op,op+k) ;
reverse(right, right+k) ;
reverse(left, left+k) ;
reverse(height, height+k) ;
vector<int> aux ;
lp(i,0,n) scramble[i] = inf ;
lp(i,0,k)
{
aux.clear() ;
seg.upd(1,0,n-1,left[i], right[i] , height[i] , op[i], -inf, inf, aux ) ;
for(int j : aux ) scramble[j] = i ;
}
iota(idx, idx+n,0 ) ;
sort(idx, idx+n , cmp ) ;
lp(i,0,n) debug("%d " , idx[i] ) ;
debug("\n") ;
int curIdx = 0 ;
lp(i,0,k)
{
seg2.upd( 1 , 0 , n-1 , left[i] , right[i] , height[i] , op[i] ) ;
while(curIdx < n && scramble[ idx[curIdx] ] == i+1 )
{
debug("Processing %d\n", idx[curIdx] ) ;
int curL = -inf , curR = inf ;
seg2.qry( 1 , 0 , n-1 , curL , curR , idx[curIdx] ) ;
if( op[i+1] == 1 ) finalHeight[ idx[curIdx] ] = curR ;
else finalHeight[ idx[curIdx] ] = curL ;
curIdx ++ ;
}
}
lp(i,0,n)
if( scramble[i] == inf )
{
finalHeight[i] = 0;
int curR = inf ;
seg2.qry( 1 , 0 , n-1 , finalHeight[i], curR, i ) ;
}
return ;
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:190:32: warning: left operand of comma operator has no effect [-Wunused-value]
lp(i,0,n) debug("%d " , idx[i] ) ;
^
wall.cpp:191:15: warning: statement has no effect [-Wunused-value]
debug("\n") ;
^
wall.cpp:202:40: warning: left operand of comma operator has no effect [-Wunused-value]
debug("Processing %d\n", idx[curIdx] ) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
219512 KB |
Output is correct |
| 2 |
Correct |
219 ms |
219696 KB |
Output is correct |
| 3 |
Incorrect |
220 ms |
219512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
219628 KB |
Output is correct |
| 2 |
Correct |
371 ms |
233188 KB |
Output is correct |
| 3 |
Execution timed out |
3053 ms |
226856 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
219632 KB |
Output is correct |
| 2 |
Correct |
193 ms |
219640 KB |
Output is correct |
| 3 |
Incorrect |
196 ms |
219844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
261 ms |
219556 KB |
Output is correct |
| 2 |
Correct |
194 ms |
219640 KB |
Output is correct |
| 3 |
Incorrect |
196 ms |
219636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
