oj.uz

Submission #661653

# Submission time Handle Problem Language Result Execution time Memory
661653 2022-11-26T03:33:59 Z guagua0407 Wall (IOI14_wall) C++17
100 / 100
 960 ms 69712 KB 
/*
希望全國賽不要墊底
*/
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int mxh=0x3f3f3f3f;

const int mxn=2e6+5;
pair<int,int> segtree[8000080];

void push(int v){
    segtree[v*2].f=max(segtree[v*2].f,segtree[v].f);
    segtree[v*2].s=min(segtree[v*2].s,segtree[v].s);
    segtree[v*2].f=min(segtree[v*2].f,segtree[v].s);
    segtree[v*2].s=max(segtree[v*2].s,segtree[v].f);
    segtree[v*2+1].f=max(segtree[v*2+1].f,segtree[v].f);
    segtree[v*2+1].s=min(segtree[v*2+1].s,segtree[v].s);
    segtree[v*2+1].f=min(segtree[v*2+1].f,segtree[v].s);
    segtree[v*2+1].s=max(segtree[v*2+1].s,segtree[v].f);
    segtree[v].f=0;
    segtree[v].s=mxh;
}

void update(int type,int tl,int tr,int h,int l,int r,int v=1){
    if(tl>tr){
        return;
    }
    if(tl<=l and r<=tr){
        if(type==1){
        	segtree[v].f=max(segtree[v].f,h);
        	segtree[v].s=max(segtree[v].s,h);
        }
        else{
        	segtree[v].s=min(segtree[v].s,h);
        	segtree[v].f=min(segtree[v].f,h);
        }
        return;
    }
    push(v);
    int mid=(l+r)/2;
    update(type,tl,min(mid,tr),h,l,mid,v*2);
    update(type,max(mid+1,tl),tr,h,mid+1,r,v*2+1);
}

ll query(int pos,int l,int r,int v=1){
    if(l==r){
        return min(segtree[v].f,segtree[v].s);
    } 
    push(v);
    int mid=(l+r)/2;
    if(pos<=mid) return query(pos,l,mid,v*2);
    else return query(pos,mid+1,r,v*2+1);
}

void buildWall(int n,int k,int op[],int l[],int r[],int h[], int final[]){
for(int i=0;i<k;i++){
        update(op[i],l[i],r[i],h[i],0,n-1);
    }
    for(int i=0;i<n;i++){
        final[i]=query(i,0,n-1);
    }
}

/*int main() {_
    //setIO("wayne");
	int op[6]={1,2,2,1,1,2};
	int l[6]={1,4,3,0,2,6};
	int r[6]={8,9,6,5,2,7};
	int h[6]={4,1,5,3,5,0};
	int final[10];
    buildWall(n,k,op,l,r,h,final);
    for(int i=0;i<n;i++){
        cout<<final[i]<<' ';
    }
    return 0;   
}*/
//maybe its multiset not set

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 130 ms 8396 KB Output is correct
3 Correct 150 ms 4412 KB Output is correct
4 Correct 415 ms 10960 KB Output is correct
5 Correct 269 ms 11468 KB Output is correct
6 Correct 262 ms 11472 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 280 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 129 ms 8276 KB Output is correct
9 Correct 158 ms 4428 KB Output is correct
10 Correct 416 ms 10988 KB Output is correct
11 Correct 294 ms 11468 KB Output is correct
12 Correct 260 ms 11568 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 133 ms 8348 KB Output is correct
15 Correct 31 ms 1620 KB Output is correct
16 Correct 407 ms 11340 KB Output is correct
17 Correct 286 ms 11316 KB Output is correct
18 Correct 272 ms 11236 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 128 ms 8364 KB Output is correct
9 Correct 152 ms 4456 KB Output is correct
10 Correct 438 ms 10960 KB Output is correct
11 Correct 269 ms 11468 KB Output is correct
12 Correct 267 ms 11496 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 133 ms 8328 KB Output is correct
15 Correct 27 ms 1608 KB Output is correct
16 Correct 421 ms 11308 KB Output is correct
17 Correct 278 ms 11276 KB Output is correct
18 Correct 289 ms 11316 KB Output is correct
19 Correct 897 ms 59376 KB Output is correct
20 Correct 910 ms 67196 KB Output is correct
21 Correct 892 ms 69712 KB Output is correct
22 Correct 878 ms 67012 KB Output is correct
23 Correct 960 ms 67036 KB Output is correct
24 Correct 875 ms 66952 KB Output is correct
25 Correct 874 ms 67020 KB Output is correct
26 Correct 882 ms 69440 KB Output is correct
27 Correct 896 ms 69696 KB Output is correct
28 Correct 877 ms 67108 KB Output is correct
29 Correct 867 ms 67100 KB Output is correct
30 Correct 869 ms 67024 KB Output is correct