oj.uz

Submission #227782

# Submission time Handle Problem Language Result Execution time Memory
227782 2020-04-28T19:04:25 Z 2fat2code Wall (IOI14_wall) C++17
100 / 100
 723 ms 67196 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 u[4*nmax],d[4*nmax],ans[nmax],lazy[4*nmax];
 
void lazi(int nod,int up,int down){
    d[nod]=min(d[nod],down);
    d[nod]=max(d[nod],up);
    u[nod]=max(u[nod],up);
    u[nod]=min(u[nod],down);
}
 
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){
            u[nod]=max(u[nod],h);
            d[nod]=max(d[nod],h);
        }
        else{
            u[nod]=min(u[nod],h);
            d[nod]=min(d[nod],h);
        }
    }
    else{
        lazi(2*nod,u[nod],d[nod]);
        lazi(2*nod+1,u[nod],d[nod]);
        u[nod]=0;
        d[nod]=1e18;
        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);
    }
}
 
void complete(int l,int r,int nod){
    if(l!=r){
        int mid=l+(r-l)/2;
        lazi(2*nod,u[nod],d[nod]);
        lazi(2*nod+1,u[nod],d[nod]);
        complete(l,mid,2*nod);
        complete(mid+1,r,2*nod+1);
    }
    else{
        ans[l]=min(u[nod],d[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:46:16: warning: overflow in implicit constant conversion [-Woverflow]
         d[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 9 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 175 ms 8316 KB Output is correct
3 Correct 179 ms 4472 KB Output is correct
4 Correct 469 ms 11384 KB Output is correct
5 Correct 306 ms 11896 KB Output is correct
6 Correct 294 ms 11896 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 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 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 176 ms 8360 KB Output is correct
9 Correct 177 ms 4472 KB Output is correct
10 Correct 468 ms 11384 KB Output is correct
11 Correct 315 ms 11772 KB Output is correct
12 Correct 300 ms 11896 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 176 ms 8376 KB Output is correct
15 Correct 33 ms 1656 KB Output is correct
16 Correct 486 ms 11640 KB Output is correct
17 Correct 298 ms 11640 KB Output is correct
18 Correct 301 ms 11640 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 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 6 ms 384 KB Output is correct
8 Correct 178 ms 8312 KB Output is correct
9 Correct 188 ms 4476 KB Output is correct
10 Correct 482 ms 11384 KB Output is correct
11 Correct 316 ms 11896 KB Output is correct
12 Correct 311 ms 11900 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 176 ms 8312 KB Output is correct
15 Correct 32 ms 1664 KB Output is correct
16 Correct 484 ms 11640 KB Output is correct
17 Correct 306 ms 11640 KB Output is correct
18 Correct 302 ms 11640 KB Output is correct
19 Correct 723 ms 67196 KB Output is correct
20 Correct 705 ms 64636 KB Output is correct
21 Correct 722 ms 67192 KB Output is correct
22 Correct 688 ms 64632 KB Output is correct
23 Correct 698 ms 64632 KB Output is correct
24 Correct 690 ms 64608 KB Output is correct
25 Correct 706 ms 64632 KB Output is correct
26 Correct 696 ms 67100 KB Output is correct
27 Correct 698 ms 67192 KB Output is correct
28 Correct 698 ms 64504 KB Output is correct
29 Correct 687 ms 64760 KB Output is correct
30 Correct 679 ms 64756 KB Output is correct