oj.uz

Submission #81766

# Submission time Handle Problem Language Result Execution time Memory
81766 2018-10-26T13:20:27 Z chelly Wall (IOI14_wall) C++11
61 / 100
 969 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[6000000];

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 256 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 10 ms 2156 KB Output is correct
5 Correct 8 ms 2292 KB Output is correct
6 Correct 8 ms 2424 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2424 KB Output is correct
2 Correct 167 ms 14708 KB Output is correct
3 Correct 234 ms 16564 KB Output is correct
4 Correct 753 ms 38956 KB Output is correct
5 Correct 382 ms 49656 KB Output is correct
6 Correct 350 ms 58036 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 58036 KB Output is correct
2 Correct 4 ms 58036 KB Output is correct
3 Correct 4 ms 58036 KB Output is correct
4 Correct 10 ms 58036 KB Output is correct
5 Correct 8 ms 58036 KB Output is correct
6 Correct 8 ms 58036 KB Output is correct
7 Correct 3 ms 58036 KB Output is correct
8 Correct 173 ms 58036 KB Output is correct
9 Correct 272 ms 58036 KB Output is correct
10 Correct 706 ms 67956 KB Output is correct
11 Correct 337 ms 68532 KB Output is correct
12 Correct 339 ms 68660 KB Output is correct
13 Correct 2 ms 68660 KB Output is correct
14 Correct 173 ms 68660 KB Output is correct
15 Correct 42 ms 68660 KB Output is correct
16 Correct 812 ms 68660 KB Output is correct
17 Correct 347 ms 68660 KB Output is correct
18 Correct 332 ms 68660 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68660 KB Output is correct
2 Correct 4 ms 68660 KB Output is correct
3 Correct 4 ms 68660 KB Output is correct
4 Correct 10 ms 68660 KB Output is correct
5 Correct 8 ms 68660 KB Output is correct
6 Correct 9 ms 68660 KB Output is correct
7 Correct 2 ms 68660 KB Output is correct
8 Correct 182 ms 68660 KB Output is correct
9 Correct 252 ms 68660 KB Output is correct
10 Correct 669 ms 68660 KB Output is correct
11 Correct 404 ms 68660 KB Output is correct
12 Correct 321 ms 68660 KB Output is correct
13 Correct 2 ms 68660 KB Output is correct
14 Correct 178 ms 68660 KB Output is correct
15 Correct 44 ms 68660 KB Output is correct
16 Correct 766 ms 68660 KB Output is correct
17 Correct 336 ms 68660 KB Output is correct
18 Correct 311 ms 68660 KB Output is correct
19 Runtime error 969 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -