oj.uz

답안 #81763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81763 2018-10-26T13:18:34 Z chelly 벽 (IOI14_wall) C++11
61 / 100
 1029 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 10 ms 2012 KB Output is correct
5 Correct 8 ms 2152 KB Output is correct
6 Correct 9 ms 2236 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2236 KB Output is correct
2 Correct 180 ms 14564 KB Output is correct
3 Correct 233 ms 16440 KB Output is correct
4 Correct 667 ms 38796 KB Output is correct
5 Correct 330 ms 49568 KB Output is correct
6 Correct 319 ms 58144 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 58144 KB Output is correct
2 Correct 4 ms 58144 KB Output is correct
3 Correct 4 ms 58144 KB Output is correct
4 Correct 10 ms 58144 KB Output is correct
5 Correct 8 ms 58144 KB Output is correct
6 Correct 8 ms 58144 KB Output is correct
7 Correct 2 ms 58144 KB Output is correct
8 Correct 173 ms 58144 KB Output is correct
9 Correct 229 ms 58144 KB Output is correct
10 Correct 649 ms 77192 KB Output is correct
11 Correct 344 ms 87932 KB Output is correct
12 Correct 315 ms 96580 KB Output is correct
13 Correct 3 ms 96580 KB Output is correct
14 Correct 188 ms 96580 KB Output is correct
15 Correct 44 ms 96580 KB Output is correct
16 Correct 768 ms 112344 KB Output is correct
17 Correct 341 ms 121468 KB Output is correct
18 Correct 325 ms 130640 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 130640 KB Output is correct
2 Correct 4 ms 130640 KB Output is correct
3 Correct 5 ms 130640 KB Output is correct
4 Correct 16 ms 130640 KB Output is correct
5 Correct 8 ms 130640 KB Output is correct
6 Correct 9 ms 130640 KB Output is correct
7 Correct 2 ms 130640 KB Output is correct
8 Correct 180 ms 130640 KB Output is correct
9 Correct 246 ms 130640 KB Output is correct
10 Correct 671 ms 149756 KB Output is correct
11 Correct 344 ms 160580 KB Output is correct
12 Correct 310 ms 169180 KB Output is correct
13 Correct 2 ms 169180 KB Output is correct
14 Correct 184 ms 169180 KB Output is correct
15 Correct 43 ms 169180 KB Output is correct
16 Correct 785 ms 185024 KB Output is correct
17 Correct 340 ms 194004 KB Output is correct
18 Correct 334 ms 202920 KB Output is correct
19 Runtime error 1029 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 -