oj.uz

Submission #247632

# Submission time Handle Problem Language Result Execution time Memory
247632 2020-07-11T17:31:41 Z LittleFlowers__ Wall (IOI14_wall) C++17
100 / 100
 767 ms 69624 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);

#include "wall.h"

const int INF=1e9,
          N=2000010;

int add[N*4],rev[N*4];

void Add(int &i,int &j,int t){
    if(j<=t){
        i=j=t;
        //i=t;
        //j=INF;
    } else{
        i=max(i,t);
    }
}
void Rev(int &i,int &j,int t){
    j=min(j,t);
}

void join(int i,int j){
    Add(add[i],rev[i],add[j]);
    Rev(add[i],rev[i],rev[j]);
}

void upd(int s,int l,int r,int u,int v,int op,int h){
    if(l>v||u>r) return;
    if(u<=l&&r<=v){
        if(op==1){
            Add(add[s],rev[s],h);
        } else{
            Rev(add[s],rev[s],h);
        }
        return;
    }
    join(2*s,s); join(2*s+1,s);
    add[s]=-INF;
    rev[s]=INF;
    int m=(l+r)/2;
    upd(2*s,l,m,u,v,op,h); upd(2*s+1,m+1,r,u,v,op,h);
}
void build(int s,int l,int r){
    add[s]=0; rev[s]=INF;
    if(l==r){
        return;
    }
    int m=(l+r)/2;
    build(2*s,l,m); build(2*s+1,m+1,r);
}
void get(int s,int l,int r,int ans[]){
    if(l==r){
        ans[l]=min(add[s],rev[s]);
        return;
    }
    int m=(l+r)/2;
    join(2*s,s); join(2*s+1,s);
    get(2*s,l,m,ans); get(2*s+1,m+1,r,ans);
}

void buildWall(int n,int k,int op[],int l[],int r[],int h[],int ans[]){
    forinc(i,0,k-1){
        upd(1,0,n-1,l[i],r[i],op[i],h[i]);
    }
    /**

    //cerr<<add[1]<<" "<<rev[1];
    //cout<<add[3]<<" "<<rev[3];
    join(3,1);
    //Add(add[3],rev[3],1);
    //+ -INF -1

    +2 -INF
    +1 -INF

    +6 -4 +4

    +2 -4 + 4

    >= - INF <=1 +1
        = 1
    //cout<<add[3]<<" "<<rev[3];
    //gg
    //join(6,3);
    //cout<<add[6]<<" "<<rev[6];
    gg
    join(1,3);
    gg
    */
    get(1,0,n-1,ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 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 10 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 190 ms 13980 KB Output is correct
3 Correct 192 ms 7928 KB Output is correct
4 Correct 495 ms 20472 KB Output is correct
5 Correct 335 ms 21496 KB Output is correct
6 Correct 322 ms 19704 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 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 182 ms 14048 KB Output is correct
9 Correct 203 ms 8184 KB Output is correct
10 Correct 507 ms 20420 KB Output is correct
11 Correct 340 ms 21496 KB Output is correct
12 Correct 315 ms 19960 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 183 ms 13944 KB Output is correct
15 Correct 38 ms 2040 KB Output is correct
16 Correct 596 ms 20652 KB Output is correct
17 Correct 339 ms 20088 KB Output is correct
18 Correct 318 ms 20088 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 11 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 186 ms 14072 KB Output is correct
9 Correct 187 ms 8056 KB Output is correct
10 Correct 488 ms 20452 KB Output is correct
11 Correct 339 ms 21496 KB Output is correct
12 Correct 317 ms 20088 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 186 ms 14048 KB Output is correct
15 Correct 38 ms 2040 KB Output is correct
16 Correct 588 ms 20732 KB Output is correct
17 Correct 317 ms 20108 KB Output is correct
18 Correct 329 ms 20088 KB Output is correct
19 Correct 718 ms 69496 KB Output is correct
20 Correct 719 ms 67004 KB Output is correct
21 Correct 756 ms 69624 KB Output is correct
22 Correct 725 ms 67256 KB Output is correct
23 Correct 738 ms 67224 KB Output is correct
24 Correct 722 ms 67320 KB Output is correct
25 Correct 724 ms 67104 KB Output is correct
26 Correct 747 ms 69496 KB Output is correct
27 Correct 767 ms 69624 KB Output is correct
28 Correct 738 ms 67192 KB Output is correct
29 Correct 725 ms 67064 KB Output is correct
30 Correct 723 ms 67192 KB Output is correct