oj.uz

Submission #444395

# Submission time Handle Problem Language Result Execution time Memory
444395 2021-07-14T00:36:48 Z FEDIKUS Wall (IOI14_wall) C++17
100 / 100
 1045 ms 99356 KB 
#include "wall.h"

#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

const int maxn=2e6+10;
pii seg[4*maxn];
int n;

pii comb(pii a,pii b){
    if(b==mp(-1,-1)) return a;
    pii ret=mp(min(a.xx,b.xx),max(a.yy,b.yy));
    if(ret.xx<ret.yy){
        if(ret.xx==a.xx) ret.yy=a.xx;
        else ret.xx=a.yy;
    }
    return ret;
}

void push(int ind){
    if(seg[ind]==mp(-1,-1)) return;
    seg[2*ind]=comb(seg[ind],seg[2*ind]);
    seg[2*ind+1]=comb(seg[ind],seg[2*ind+1]);
    seg[ind]=mp(-1,-1);
}

void update(int tl,int tr,int hg,int hd,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(tl<=l && r<=tr){
        seg[ind]=comb(mp(hg,hd),seg[ind]);
        return;
    }
    int mid=l+(r-l)/2;
    if(tl<=mid) update(tl,tr,hg,hd,2*ind,l,mid);
    if(tr>mid) update(tl,tr,hg,hd,2*ind+1,mid+1,r);
}

int query(int t,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(l==r) return seg[ind].xx;
    int mid=l+(r-l)/2;
    if(t<=mid) return query(t,2*ind,l,mid);
    if(t>mid) return query(t,2*ind+1,mid+1,r);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;
    for(int i=0;i<4*maxn;i++) seg[i]=mp(-1,-1);
    update(0,n-1,0,0);
    for(int i=0;i<k;i++){
        if(op[i]==1){
            update(left[i],right[i],INT_MAX,height[i]);
        }else{
            update(left[i],right[i],height[i],INT_MIN);
        }
    }
    for(int i=0;i<n;i++) finalHeight[i]=query(i);
    return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Compilation message

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62792 KB Output is correct
2 Correct 37 ms 62956 KB Output is correct
3 Correct 37 ms 62828 KB Output is correct
4 Correct 44 ms 63096 KB Output is correct
5 Correct 42 ms 63092 KB Output is correct
6 Correct 43 ms 63148 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62788 KB Output is correct
2 Correct 193 ms 70680 KB Output is correct
3 Correct 263 ms 66256 KB Output is correct
4 Correct 758 ms 80924 KB Output is correct
5 Correct 349 ms 82012 KB Output is correct
6 Correct 343 ms 80404 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62796 KB Output is correct
2 Correct 35 ms 62924 KB Output is correct
3 Correct 35 ms 62868 KB Output is correct
4 Correct 42 ms 63096 KB Output is correct
5 Correct 41 ms 63064 KB Output is correct
6 Correct 40 ms 63084 KB Output is correct
7 Correct 36 ms 62788 KB Output is correct
8 Correct 193 ms 76500 KB Output is correct
9 Correct 259 ms 70084 KB Output is correct
10 Correct 753 ms 80860 KB Output is correct
11 Correct 343 ms 81948 KB Output is correct
12 Correct 321 ms 80504 KB Output is correct
13 Correct 33 ms 62808 KB Output is correct
14 Correct 195 ms 76460 KB Output is correct
15 Correct 74 ms 64012 KB Output is correct
16 Correct 792 ms 81216 KB Output is correct
17 Correct 336 ms 80628 KB Output is correct
18 Correct 349 ms 80540 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62904 KB Output is correct
2 Correct 35 ms 62916 KB Output is correct
3 Correct 34 ms 62832 KB Output is correct
4 Correct 41 ms 63096 KB Output is correct
5 Correct 44 ms 63072 KB Output is correct
6 Correct 38 ms 63044 KB Output is correct
7 Correct 33 ms 62840 KB Output is correct
8 Correct 196 ms 76448 KB Output is correct
9 Correct 257 ms 70012 KB Output is correct
10 Correct 768 ms 81036 KB Output is correct
11 Correct 347 ms 81936 KB Output is correct
12 Correct 319 ms 80452 KB Output is correct
13 Correct 32 ms 62788 KB Output is correct
14 Correct 195 ms 76524 KB Output is correct
15 Correct 72 ms 64104 KB Output is correct
16 Correct 782 ms 81168 KB Output is correct
17 Correct 361 ms 80576 KB Output is correct
18 Correct 324 ms 80684 KB Output is correct
19 Correct 1006 ms 99244 KB Output is correct
20 Correct 996 ms 96776 KB Output is correct
21 Correct 1004 ms 99220 KB Output is correct
22 Correct 990 ms 96856 KB Output is correct
23 Correct 992 ms 96848 KB Output is correct
24 Correct 1045 ms 96784 KB Output is correct
25 Correct 992 ms 96836 KB Output is correct
26 Correct 1022 ms 99356 KB Output is correct
27 Correct 993 ms 99252 KB Output is correct
28 Correct 986 ms 96692 KB Output is correct
29 Correct 993 ms 96704 KB Output is correct
30 Correct 995 ms 96888 KB Output is correct