oj.uz

Submission #247579

# Submission time Handle Problem Language Result Execution time Memory
247579 2020-07-11T16:38:38 Z LittleFlowers__ Wall (IOI14_wall) C++17
24 / 100
 537 ms 20008 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=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]);
    }
    get(1,0,n-1,ans);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 198 ms 8176 KB Output is correct
3 Correct 211 ms 4268 KB Output is correct
4 Correct 537 ms 10816 KB Output is correct
5 Correct 449 ms 18344 KB Output is correct
6 Correct 437 ms 20008 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 456 KB Output is correct
3 Incorrect 9 ms 424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 7 ms 464 KB Output is correct
3 Incorrect 7 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -