oj.uz

Submission #81765

# Submission time Handle Problem Language Result Execution time Memory
81765 2018-10-26T13:19:17 Z chelly Wall (IOI14_wall) C++17
61 / 100
 963 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;
#define mid (seg[rt].l+seg[rt].r)/2
struct Node{ int l, r, mx, mn;
bool lazymx, lazymn; };
int n, k, op[2000005], l[2000005], r[2000005], height[2000005], finalHeight[2000005];
Node seg[8000000];

void build (int l, int r, int rt){
    //cout<<l<<" "<<r<<" "<<rt<<endl;
    seg[rt].l = l;
    seg[rt].r = r;
    if (l==r) return;
    build (l, mid, 2*rt);
    build (mid+1, r, 2*rt+1);
}
void pushup (int rt){
    seg[rt].mx = max(seg[2*rt].mx, seg[2*rt+1].mx);
    seg[rt].mn = min(seg[2*rt].mn, seg[2*rt+1].mn);
}
void lazy (int rt){
    if (seg[rt].lazymn){
        seg[2*rt].mn = max(seg[2*rt].mn, seg[rt].mn);
        seg[2*rt].mx = max(seg[2*rt].mx, seg[2*rt].mn);
        seg[2*rt+1].mn = max(seg[2*rt+1].mn, seg[rt].mn);
        seg[2*rt+1].mx = max(seg[2*rt+1].mx, seg[2*rt+1].mn);
        seg[2*rt].lazymn=true;
        seg[2*rt+1].lazymn=true;
        seg[rt].lazymn=false;
    }
    if (seg[rt].lazymx){
        seg[2*rt].mx = min(seg[2*rt].mx, seg[rt].mx);
        seg[2*rt].mn = min(seg[2*rt].mx, seg[2*rt].mn);
        seg[2*rt+1].mx = min(seg[2*rt+1].mx, seg[rt].mx);
        seg[2*rt+1].mn = min(seg[2*rt+1].mx, seg[2*rt+1].mn);
        seg[2*rt].lazymx=true;
        seg[2*rt+1].lazymx=true;
        seg[rt].lazymx=false;
    }
}
void add (int l, int r, int v, int rt){
    if (seg[rt].l==l&&seg[rt].r==r){
        seg[rt].mn = max(seg[rt].mn, v);
        seg[rt].mx = max(seg[rt].mx, seg[rt].mn);
        seg[rt].lazymn = true;
        return;
    }
    if(seg[rt].lazymn||seg[rt].lazymx) lazy(rt);
    if (r<=mid) add (l, r, v, 2*rt);
    else if (l>mid) add(l, r, v, 2*rt+1);
    else{
        add (l, mid, v, 2*rt);
        add (mid+1, r, v, 2*rt+1);
    }
    pushup(rt);
}
void rem (int l, int r, int v, int rt){
    if (seg[rt].l==l&&seg[rt].r==r){
        seg[rt].mx = min(seg[rt].mx, v);
        seg[rt].mn = min(seg[rt].mx, seg[rt].mn);
        seg[rt].lazymx = true;
        return;
    }
    if(seg[rt].lazymn||seg[rt].lazymx) lazy(rt);
    if (r<=mid) rem(l, r, v, 2*rt);
    else if (l>mid) rem(l, r, v, 2*rt+1);
    else{
        rem (l, mid, v, 2*rt);
        rem (mid+1, r, v, 2*rt+1);
    }
    pushup(rt);
}
void print (int rt){
    cout<<seg[rt].l<<" "<<seg[rt].r<<" "<<seg[rt].mx<<" "<<seg[rt].mn<<" "<<seg[rt].lazymx<<" "<<seg[rt].lazymn<<endl;
    if (seg[rt].l==seg[rt].r) return;
    print(2*rt); print(2*rt+1);
}
void dfs (int rt, int ar[]){
    if (seg[rt].lazymn||seg[rt].lazymx) lazy(rt);
    if (seg[rt].l==seg[rt].r){
        ar[seg[rt].l] = seg[rt].mn;
        return;
    }
    dfs (2*rt, ar); dfs (2*rt+1, ar);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build (0, n-1, 1);
    for (int i = 0; i<k; i++){
        if (op[i]==1){
            add(left[i], right[i], height[i], 1);
        }
        else{
            rem(left[i], right[i], height[i], 1);
        }
        //print(1);
        //cout<<endl;
        /*dfs(1, finalHeight);
        for (int i = 0; i<n; i++){
            cout<<finalHeight[i]<<" ";
        }
        cout<<endl;*/
    }
    dfs (1, finalHeight);
    /*for (int i = 0; i<n; i++){
        cout<<finalHeight[i]<<" ";
    }
    cout<<endl;*/
}
/*
int main()
{
    cin>>n>>k;
    for (int i = 0; i<k; i++){
        cin>>op[i]>>l[i]>>r[i]>>height[i];
    }
    buildWall(n, k, op, l, r, height, finalHeight);
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 13 ms 2048 KB Output is correct
5 Correct 8 ms 2148 KB Output is correct
6 Correct 10 ms 2232 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2232 KB Output is correct
2 Correct 193 ms 14528 KB Output is correct
3 Correct 233 ms 16492 KB Output is correct
4 Correct 804 ms 39052 KB Output is correct
5 Correct 402 ms 49496 KB Output is correct
6 Correct 343 ms 58100 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 58100 KB Output is correct
2 Correct 4 ms 58100 KB Output is correct
3 Correct 4 ms 58100 KB Output is correct
4 Correct 10 ms 58100 KB Output is correct
5 Correct 10 ms 58100 KB Output is correct
6 Correct 8 ms 58100 KB Output is correct
7 Correct 2 ms 58100 KB Output is correct
8 Correct 165 ms 58100 KB Output is correct
9 Correct 232 ms 58100 KB Output is correct
10 Correct 682 ms 77320 KB Output is correct
11 Correct 361 ms 87912 KB Output is correct
12 Correct 352 ms 96464 KB Output is correct
13 Correct 2 ms 96464 KB Output is correct
14 Correct 171 ms 96464 KB Output is correct
15 Correct 42 ms 96464 KB Output is correct
16 Correct 746 ms 112236 KB Output is correct
17 Correct 322 ms 121288 KB Output is correct
18 Correct 338 ms 130188 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 130188 KB Output is correct
2 Correct 4 ms 130188 KB Output is correct
3 Correct 3 ms 130188 KB Output is correct
4 Correct 10 ms 130188 KB Output is correct
5 Correct 8 ms 130188 KB Output is correct
6 Correct 8 ms 130188 KB Output is correct
7 Correct 2 ms 130188 KB Output is correct
8 Correct 175 ms 130188 KB Output is correct
9 Correct 262 ms 130188 KB Output is correct
10 Correct 694 ms 140480 KB Output is correct
11 Correct 338 ms 141024 KB Output is correct
12 Correct 308 ms 141024 KB Output is correct
13 Correct 2 ms 141024 KB Output is correct
14 Correct 176 ms 141024 KB Output is correct
15 Correct 42 ms 141024 KB Output is correct
16 Correct 707 ms 141024 KB Output is correct
17 Correct 314 ms 141024 KB Output is correct
18 Correct 328 ms 141024 KB Output is correct
19 Runtime error 963 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Halted 0 ms 0 KB -