oj.uz

Submission #90393

# Submission time Handle Problem Language Result Execution time Memory
90393 2018-12-21T13:19:43 Z Retro3014 Wall (IOI14_wall) C++17
100 / 100
 1202 ms 126900 KB 
#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define INF 100000
#define MAX_N 2000000
struct S{
    int l, r;
    int nmin, nmax;
    int from;
};
vector<S> seg;
int ans[MAX_N+1];


void init(int x, int y){
    int idx=(int)seg.size();
    seg.push_back({-1, -1, 0, 0, -1});
    if(x==y){
        return;
    }
    int m=(x+y)/2;
    if(x<=m){
        seg[idx].l=(int)seg.size();
        init(x, m);
        seg[seg[idx].l].from=idx;
    }
    if(m+1<=y){
        seg[idx].r=(int)seg.size();
        init(m+1, y);
        seg[seg[idx].r].from=idx;
    }
    return;
}

void updaten(int x){
    if(seg[x].from!=-1){
        int t=seg[x].from;
        if(seg[t].nmax<seg[x].nmax){
            seg[x].nmax=seg[t].nmax;
        }
        if(seg[t].nmax<seg[x].nmin){
            seg[x].nmin=seg[t].nmax;
        }
        if(seg[t].nmin>seg[x].nmax){
            seg[x].nmax=seg[t].nmin;
        }
        if(seg[t].nmin>seg[x].nmin){
            seg[x].nmin=seg[t].nmin;
        }
    }
    return;
}

void update(int idx, int li, int ri, int data, int nx, int ny){
    //int nx=seg[idx].s, ny=seg[idx].e;
    if(seg[idx].l!=-1){
        updaten(seg[idx].l);
    }
    if(seg[idx].r!=-1){
        updaten(seg[idx].r);
    }
    if(li>ny || ri<nx)  return;
    if(data>0){
        if(seg[idx].nmax<data){
            seg[idx].nmax=data;
        }
    }else{
        data=-data;
        if(seg[idx].nmin>data){
            seg[idx].nmin=data;
        }
        data=-data;
    }
    if(li<=nx && ri>=ny) {
        if(data>0){
            if(seg[idx].nmin<data){
                seg[idx].nmin=data;
            }
        }else{
            data=-data;
            if(seg[idx].nmax>data){
                seg[idx].nmax=data;
            }
            data=-data;
        }
        return;
    }
    if(seg[idx].l!=-1){
        update(seg[idx].l, li, ri, data, nx, (nx+ny)/2);
    }
    if(seg[idx].r!=-1){
        update(seg[idx].r, li, ri, data, (nx+ny)/2+1, ny);
    }
    seg[idx].nmax=max((seg[idx].r==-1?-1:seg[seg[idx].r].nmax), (seg[idx].l==-1?-1:seg[seg[idx].l].nmax));
    seg[idx].nmin=min((seg[idx].r==-1?INF+1:seg[seg[idx].r].nmin), (seg[idx].l==-1?INF+1:seg[seg[idx].l].nmin));
}

void find_ans(int idx, int nx, int ny){
    if(seg[idx].l!=-1){
        updaten(seg[idx].l);
    }
    if(seg[idx].r!=-1){
        updaten(seg[idx].r);
    }
    if(nx==ny){
        ans[nx]=seg[idx].nmax;
        return;
    }
    if(seg[idx].l!=-1){
        find_ans(seg[idx].l, nx, (nx+ny)/2);
    }
    if(seg[idx].r!=-1){
        find_ans(seg[idx].r, (nx+ny)/2+1, ny);
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    init(0, n-1);
    for(int i=0; i<k; i++){
        if(op[i]==1){
            update(0, left[i], right[i], height[i], 0, n-1);
        }else{
            update(0, left[i], right[i], -height[i], 0, n-1);
        }
    }
    find_ans(0, 0, n-1);
    for(int i=0; i<n; i++){
        finalHeight[i]=ans[i];
    }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 11 ms 1412 KB Output is correct
5 Correct 9 ms 1552 KB Output is correct
6 Correct 9 ms 1704 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1704 KB Output is correct
2 Correct 146 ms 8700 KB Output is correct
3 Correct 260 ms 8700 KB Output is correct
4 Correct 799 ms 17484 KB Output is correct
5 Correct 434 ms 17728 KB Output is correct
6 Correct 423 ms 17872 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17872 KB Output is correct
2 Correct 3 ms 17872 KB Output is correct
3 Correct 4 ms 17872 KB Output is correct
4 Correct 12 ms 17872 KB Output is correct
5 Correct 9 ms 17872 KB Output is correct
6 Correct 9 ms 17872 KB Output is correct
7 Correct 2 ms 17872 KB Output is correct
8 Correct 146 ms 17872 KB Output is correct
9 Correct 257 ms 17872 KB Output is correct
10 Correct 779 ms 17872 KB Output is correct
11 Correct 435 ms 17872 KB Output is correct
12 Correct 426 ms 17940 KB Output is correct
13 Correct 2 ms 17940 KB Output is correct
14 Correct 149 ms 17940 KB Output is correct
15 Correct 55 ms 17940 KB Output is correct
16 Correct 1008 ms 17940 KB Output is correct
17 Correct 511 ms 17940 KB Output is correct
18 Correct 446 ms 17940 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17940 KB Output is correct
2 Correct 3 ms 17940 KB Output is correct
3 Correct 3 ms 17940 KB Output is correct
4 Correct 11 ms 17940 KB Output is correct
5 Correct 8 ms 17940 KB Output is correct
6 Correct 8 ms 17940 KB Output is correct
7 Correct 2 ms 17940 KB Output is correct
8 Correct 141 ms 17940 KB Output is correct
9 Correct 257 ms 17940 KB Output is correct
10 Correct 810 ms 17940 KB Output is correct
11 Correct 435 ms 17940 KB Output is correct
12 Correct 420 ms 17940 KB Output is correct
13 Correct 2 ms 17940 KB Output is correct
14 Correct 145 ms 17940 KB Output is correct
15 Correct 54 ms 17940 KB Output is correct
16 Correct 1032 ms 17940 KB Output is correct
17 Correct 437 ms 17940 KB Output is correct
18 Correct 435 ms 17940 KB Output is correct
19 Correct 1159 ms 116416 KB Output is correct
20 Correct 1126 ms 116416 KB Output is correct
21 Correct 1157 ms 116456 KB Output is correct
22 Correct 1187 ms 116456 KB Output is correct
23 Correct 1181 ms 116456 KB Output is correct
24 Correct 1190 ms 116456 KB Output is correct
25 Correct 1127 ms 116456 KB Output is correct
26 Correct 1136 ms 116456 KB Output is correct
27 Correct 1140 ms 126900 KB Output is correct
28 Correct 1160 ms 126900 KB Output is correct
29 Correct 1198 ms 126900 KB Output is correct
30 Correct 1202 ms 126900 KB Output is correct