oj.uz

답안 #247565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247565 2020-07-11T16:21:33 Z LittleFlowers__ 벽 (IOI14_wall) C++17
0 / 100
 497 ms 18784 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]=-INF; 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[]){
 	build(1,0,n-1);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 189 ms 13944 KB Output is correct
3 Correct 193 ms 8056 KB Output is correct
4 Incorrect 497 ms 18784 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Incorrect 22 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 416 KB Output is correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -