oj.uz

Submission #31806

# Submission time Handle Problem Language Result Execution time Memory
31806 2017-09-09T09:34:20 Z top34051 Wall (IOI14_wall) C++14
0 / 100
 446 ms 23120 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define inf 1e9

int ans[maxn];
int ub[maxn*4], lb[maxn*4];
pair<int,int> lazy[maxn*4];

void upd(int pos,int l,int r,int ok) {
    int mid = (l+r)/2;
    int val = lazy[pos].first, type = lazy[pos].second;
    if(type==0) return ;
//    printf("------- upd %d [%d, %d] : apply {%d, %d}\n",pos,l,r,val,type);
    if(type==1) ub[pos] = max(ub[pos], val), lb[pos] = ub[pos];
    if(type==2) lb[pos] = min(lb[pos], val), ub[pos] = lb[pos];
    if(l!=r && ok) {
        upd(pos<<1,l,mid,0); upd(pos<<1|1,mid+1,r,0);
        lazy[pos<<1] = lazy[pos<<1|1] = lazy[pos];
    }
    lazy[pos] = {0,0};
//    printf("------------- cur %d [%d, %d] : %d and %d\n",pos,l,r,lb[pos],ub[pos]);
}

void build(int pos,int l,int r) {
    ub[pos] = 0; lb[pos] = 0;
    if(l==r) return ;
    int mid = (l+r)/2;
    build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
}

void update(int pos,int l,int r,int x,int y,int val,int type) {
    upd(pos,l,r,1);
    if(l>r || y<l || r<x) return ;
    if(x<=l && r<=y) {
//        printf("update %d : [%d, %d] (%d, %d) : {%d, %d}\n",pos,l,r,x,y,val,type);
        lazy[pos] = {val,type};
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,y,val,type); update(pos<<1|1,mid+1,r,x,y,val,type);
}

void query(int pos,int l,int r) {
    upd(pos,l,r,1);
    if(l==r) {
        ans[l] = lb[pos];
        return ;
    }
    int mid = (l+r)/2;
    query(pos<<1,l,mid); query(pos<<1|1,mid+1,r);
}

void buildWall(int n, int m, int type[], int L[], int R[], int val[], int ret[]) {
    int i;
    build(1,0,n-1);
    for(i=0;i<m;i++) update(1,0,n-1,L[i],R[i],val[i],type[i]);
    query(1,0,n-1);
    for(i=0;i<n;i++) ret[i] = ans[i];
    return ;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15296 KB Output is correct
2 Correct 186 ms 23120 KB Output is correct
3 Incorrect 446 ms 18692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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