oj.uz

Submission #109996

# Submission time Handle Problem Language Result Execution time Memory
109996 2019-05-08T15:02:42 Z boatinw99 Wall (IOI14_wall) C++11
100 / 100
 1046 ms 114040 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define mid (l+r>>1)
#define fi first
#define se second
const int N = 2e6+9 ,inf = 2e9;
int st[N<<2],ans[N];
pii lazy[N<<2];
void operate(pii &a,pii b)
{
    if(b.se<=a.fi)
    {
        a={b.se,b.se};
    }
    else if(a.se<=b.fi)
    {
        a={b.fi,b.fi};
    }
    else
    {
        a.fi=max(a.fi,b.fi);
        a.se=min(a.se,b.se);
    }
}
void push(int l,int r,int m)
{
    ///fi -> min ||| se -> max
    if(lazy[m].fi==-inf&&lazy[m].se==inf)return ;
    //printf("bbb l=%d r=%d (%d %d) \n",l,r,lazy[m].fi,lazy[m].se);
    st[m]=max(st[m],lazy[m].fi);
    st[m]=min(st[m],lazy[m].se);
    if(l<r)
    {
        operate(lazy[m<<1],lazy[m]);
        operate(lazy[m<<1|1],lazy[m]);
    }
    lazy[m]={-inf,inf};
}
void update(int l,int r,int x,int y,pii nw,int m)
{
    push(l,r,m);
    if(r<x||l>y)return ;
    if(l>=x&&r<=y)
    {
        lazy[m]=nw;
        //printf("aaa l=%d r=%d (%d %d) \n",l,r,lazy[m].fi,lazy[m].se);
        push(l,r,m);
        return ;
    }
    update(l,mid,x,y,nw,m<<1);
    update(mid+1,r,x,y,nw,m<<1|1);
}
void getans(int l,int r,int m)
{
    push(l,r,m);
    if(l==r)
    {
        ans[l]=st[m];
        return ;
    }
    getans(l,mid,m<<1);
    getans(mid+1,r,m<<1|1);
}
void buildWall(int n,int k,int op[],int left[],
               int right[],int height[],int finalHeight[])
{
    for(int i=0;i<N*4;i++)lazy[i]={-inf,inf};
    for(int i=0;i<k;i++)
    {
        int l = left[i] , r = right[i] ;
        if(op[i]==1)update(0,n-1,l,r,{height[i],inf},1);
        else update(0,n-1,l,r,{-inf,height[i]},1);
    }
    getans(0,n-1,1);
    for(int i=0;i<n;i++)finalHeight[i]=ans[i];
    return ;
}

Compilation message

wall.cpp: In function 'void update(int, int, int, int, pii, int)':
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:52:14: note: in expansion of macro 'mid'
     update(l,mid,x,y,nw,m<<1);
              ^~~
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:53:12: note: in expansion of macro 'mid'
     update(mid+1,r,x,y,nw,m<<1|1);
            ^~~
wall.cpp: In function 'void getans(int, int, int)':
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:63:14: note: in expansion of macro 'mid'
     getans(l,mid,m<<1);
              ^~~
wall.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
wall.cpp:64:12: note: in expansion of macro 'mid'
     getans(mid+1,r,m<<1|1);
            ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 62968 KB Output is correct
2 Correct 72 ms 63100 KB Output is correct
3 Correct 74 ms 62972 KB Output is correct
4 Correct 66 ms 63300 KB Output is correct
5 Correct 66 ms 63392 KB Output is correct
6 Correct 63 ms 63304 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 62944 KB Output is correct
2 Correct 212 ms 72172 KB Output is correct
3 Correct 344 ms 67960 KB Output is correct
4 Correct 854 ms 73976 KB Output is correct
5 Correct 351 ms 74588 KB Output is correct
6 Correct 332 ms 74360 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 59 ms 63068 KB Output is correct
3 Correct 62 ms 63068 KB Output is correct
4 Correct 83 ms 63292 KB Output is correct
5 Correct 59 ms 63336 KB Output is correct
6 Correct 61 ms 63320 KB Output is correct
7 Correct 55 ms 63012 KB Output is correct
8 Correct 243 ms 71800 KB Output is correct
9 Correct 358 ms 67804 KB Output is correct
10 Correct 839 ms 73848 KB Output is correct
11 Correct 384 ms 74384 KB Output is correct
12 Correct 355 ms 74364 KB Output is correct
13 Correct 57 ms 62972 KB Output is correct
14 Correct 228 ms 71900 KB Output is correct
15 Correct 102 ms 64456 KB Output is correct
16 Correct 1018 ms 74128 KB Output is correct
17 Correct 358 ms 74048 KB Output is correct
18 Correct 347 ms 74020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 62 ms 63096 KB Output is correct
3 Correct 61 ms 62968 KB Output is correct
4 Correct 67 ms 63288 KB Output is correct
5 Correct 60 ms 63352 KB Output is correct
6 Correct 68 ms 63352 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Correct 198 ms 71704 KB Output is correct
9 Correct 252 ms 67704 KB Output is correct
10 Correct 916 ms 73848 KB Output is correct
11 Correct 377 ms 74360 KB Output is correct
12 Correct 364 ms 74280 KB Output is correct
13 Correct 60 ms 62968 KB Output is correct
14 Correct 225 ms 71732 KB Output is correct
15 Correct 91 ms 64504 KB Output is correct
16 Correct 1046 ms 74120 KB Output is correct
17 Correct 420 ms 74000 KB Output is correct
18 Correct 374 ms 74104 KB Output is correct
19 Correct 859 ms 113936 KB Output is correct
20 Correct 728 ms 111480 KB Output is correct
21 Correct 806 ms 114004 KB Output is correct
22 Correct 789 ms 111464 KB Output is correct
23 Correct 830 ms 111428 KB Output is correct
24 Correct 804 ms 111608 KB Output is correct
25 Correct 933 ms 111608 KB Output is correct
26 Correct 850 ms 113912 KB Output is correct
27 Correct 887 ms 114040 KB Output is correct
28 Correct 893 ms 111740 KB Output is correct
29 Correct 873 ms 111568 KB Output is correct
30 Correct 803 ms 111480 KB Output is correct