oj.uz

Submission #227787

# Submission time Handle Problem Language Result Execution time Memory
227787 2020-04-28T19:40:56 Z 2fat2code Wall (IOI14_wall) C++17
100 / 100
 901 ms 67728 KB 
#include "wall.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=2000005;

int up[4*nmax],down[4*nmax],ans[nmax],lazy[4*nmax];

void lazi(int nod,int up1,int down1){
    down[nod]=max(down[nod],down1);
    down[nod]=min(down[nod],up1);
    up[nod]=min(up[nod],up1);
    up[nod]=max(up[nod],down1);
}

void update(int l,int r,int le,int ri,int op,int h,int nod){
    if(l>ri || r<le) return;
    else if(l>=le && r<=ri){
        if(op==1){
            up[nod]=max(up[nod],h);
            down[nod]=max(down[nod],h);
        }
        else{
            up[nod]=min(up[nod],h);
            down[nod]=min(down[nod],h);
        }
    }
    else{
        lazi(2*nod,up[nod],down[nod]);
        lazi(2*nod+1,up[nod],down[nod]);
        int mid=l+(r-l)/2;
        update(l,mid,le,ri,op,h,2*nod);
        update(mid+1,r,le,ri,op,h,2*nod+1);
        down[nod]=0;
        up[nod]=1e18;
    }
}

void complete(int l,int r,int nod){
    if(l!=r){
        int mid=l+(r-l)/2;
        lazi(2*nod,up[nod],down[nod]);
        lazi(2*nod+1,up[nod],down[nod]);
        complete(l,mid,2*nod);
        complete(mid+1,r,2*nod+1);
    }
    else{
        ans[l]=up[nod];
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=1;i<=k;i++){
        update(1,n,left[i-1]+1,right[i-1]+1,op[i-1],height[i-1],1);
    }
    complete(1,n,1);
    for(int i=1;i<=n;i++) finalHeight[i-1]=ans[i];
}

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:49:17: warning: overflow in implicit constant conversion [-Woverflow]
         up[nod]=1e18;
                 ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 178 ms 8568 KB Output is correct
3 Correct 180 ms 4824 KB Output is correct
4 Correct 486 ms 11628 KB Output is correct
5 Correct 315 ms 12152 KB Output is correct
6 Correct 314 ms 12152 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 177 ms 8568 KB Output is correct
9 Correct 184 ms 4728 KB Output is correct
10 Correct 501 ms 11564 KB Output is correct
11 Correct 322 ms 12256 KB Output is correct
12 Correct 303 ms 12152 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 177 ms 8568 KB Output is correct
15 Correct 33 ms 2048 KB Output is correct
16 Correct 488 ms 11848 KB Output is correct
17 Correct 304 ms 11952 KB Output is correct
18 Correct 299 ms 11896 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 175 ms 8572 KB Output is correct
9 Correct 184 ms 4728 KB Output is correct
10 Correct 513 ms 11640 KB Output is correct
11 Correct 335 ms 12320 KB Output is correct
12 Correct 301 ms 12408 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 181 ms 8824 KB Output is correct
15 Correct 35 ms 2152 KB Output is correct
16 Correct 501 ms 12204 KB Output is correct
17 Correct 349 ms 12136 KB Output is correct
18 Correct 320 ms 12072 KB Output is correct
19 Correct 721 ms 67680 KB Output is correct
20 Correct 901 ms 65400 KB Output is correct
21 Correct 698 ms 67584 KB Output is correct
22 Correct 737 ms 65144 KB Output is correct
23 Correct 690 ms 65080 KB Output is correct
24 Correct 724 ms 65272 KB Output is correct
25 Correct 699 ms 65080 KB Output is correct
26 Correct 720 ms 67728 KB Output is correct
27 Correct 723 ms 67656 KB Output is correct
28 Correct 690 ms 65272 KB Output is correct
29 Correct 672 ms 65144 KB Output is correct
30 Correct 670 ms 65108 KB Output is correct