oj.uz

Submission #306873

# Submission time Handle Problem Language Result Execution time Memory
306873 2020-09-26T12:34:08 Z juggernaut Wall (IOI14_wall) C++14
100 / 100
 813 ms 69624 KB 
#include"wall.h"
#include<bits/stdc++.h>
using namespace std;
int flag[8000000][2];
void upd(int v,int mn,int mx){
    flag[v][0]=min(max(flag[v][0],mn),mx);
	flag[v][1]=min(max(flag[v][1],mn),mx);
}
void push(int v,int l,int r){
    if(l!=r){
        upd(v<<1,flag[v][0],flag[v][1]);
        upd((v<<1)+1,flag[v][0],flag[v][1]);
    }
  	flag[v][0]=0;
  	flag[v][1]=2e9;
}
void update(int v,int l,int r,int ql,int qr,int mn,int mx){
    if(ql<=l&&r<=qr){
        upd(v,mn,mx);
        return;
    }
    if(r<ql||qr<l)return;
    push(v,l,r);
    int mid=(l+r)>>1;
    update(v<<1,l,mid,ql,qr,mn,mx);
    update((v<<1)+1,mid+1,r,ql,qr,mn,mx);
}
void build(int v,int l,int r,int* res){
    if(l==r){
        res[l]=flag[v][0];
        return;
    }
  	push(v,l,r);
    int mid=(l+r)>>1;
    build(v<<1,l,mid,res);
    build((v<<1)+1,mid+1,r,res);
}
void buildWall(int n,int k,int* type,int* l,int* r,int* h,int* res){
    for(int i=0;i<k;i++)update(1,0,n-1,l[i],r[i],(type[i]&1)?h[i]:0,(type[i]&2)?h[i]:2e9);
    build(1,0,n-1,res);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 179 ms 8184 KB Output is correct
3 Correct 192 ms 4216 KB Output is correct
4 Correct 556 ms 20552 KB Output is correct
5 Correct 357 ms 21624 KB Output is correct
6 Correct 349 ms 19960 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 181 ms 14072 KB Output is correct
9 Correct 198 ms 8060 KB Output is correct
10 Correct 534 ms 20472 KB Output is correct
11 Correct 367 ms 21496 KB Output is correct
12 Correct 334 ms 20088 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 183 ms 14040 KB Output is correct
15 Correct 32 ms 2040 KB Output is correct
16 Correct 553 ms 20760 KB Output is correct
17 Correct 344 ms 20088 KB Output is correct
18 Correct 343 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 177 ms 13944 KB Output is correct
9 Correct 193 ms 8056 KB Output is correct
10 Correct 540 ms 20472 KB Output is correct
11 Correct 353 ms 21624 KB Output is correct
12 Correct 340 ms 19968 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 181 ms 14088 KB Output is correct
15 Correct 32 ms 2048 KB Output is correct
16 Correct 539 ms 20728 KB Output is correct
17 Correct 346 ms 20088 KB Output is correct
18 Correct 347 ms 20088 KB Output is correct
19 Correct 790 ms 69624 KB Output is correct
20 Correct 777 ms 67064 KB Output is correct
21 Correct 813 ms 69624 KB Output is correct
22 Correct 781 ms 67192 KB Output is correct
23 Correct 780 ms 67320 KB Output is correct
24 Correct 776 ms 67112 KB Output is correct
25 Correct 781 ms 67064 KB Output is correct
26 Correct 799 ms 69624 KB Output is correct
27 Correct 790 ms 69624 KB Output is correct
28 Correct 785 ms 67064 KB Output is correct
29 Correct 779 ms 67192 KB Output is correct
30 Correct 784 ms 67192 KB Output is correct