oj.uz

Submission #90386

# Submission time Handle Problem Language Result Execution time Memory
90386 2018-12-21T13:08:29 Z Retro3014 Wall (IOI14_wall) C++17
61 / 100
 1206 ms 263168 KB 
#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define INF 100000

struct S{
    int s, e;
    int l, r;
    int nmin, nmax;
    int from;
};
vector<S> seg;



void init(int x, int y){
    int idx=(int)seg.size();
    seg.push_back({x, y, -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=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].r!=-1){
        update(seg[idx].r, li, ri, data);
    }
    if(seg[idx].l!=-1){
        update(seg[idx].l, li, ri, data);
    }
    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 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]);
        }else{
            update(0, left[i], right[i], -height[i]);
        }
    }
    for(int i=0; i<seg.size(); i++){
        updaten(i);
        if(seg[i].s==seg[i].e){
            finalHeight[seg[i].s]=seg[i].nmax;
        }
    }
  return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<seg.size(); i++){
                  ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 12 ms 1788 KB Output is correct
5 Correct 9 ms 1836 KB Output is correct
6 Correct 9 ms 1968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1968 KB Output is correct
2 Correct 142 ms 14556 KB Output is correct
3 Correct 282 ms 15868 KB Output is correct
4 Correct 933 ms 35348 KB Output is correct
5 Correct 438 ms 45492 KB Output is correct
6 Correct 426 ms 54328 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54328 KB Output is correct
2 Correct 3 ms 54328 KB Output is correct
3 Correct 3 ms 54328 KB Output is correct
4 Correct 11 ms 54328 KB Output is correct
5 Correct 9 ms 54328 KB Output is correct
6 Correct 9 ms 54328 KB Output is correct
7 Correct 2 ms 54328 KB Output is correct
8 Correct 138 ms 54328 KB Output is correct
9 Correct 266 ms 54328 KB Output is correct
10 Correct 917 ms 73788 KB Output is correct
11 Correct 433 ms 84028 KB Output is correct
12 Correct 428 ms 92552 KB Output is correct
13 Correct 2 ms 92552 KB Output is correct
14 Correct 144 ms 92552 KB Output is correct
15 Correct 55 ms 92552 KB Output is correct
16 Correct 1119 ms 108552 KB Output is correct
17 Correct 445 ms 117836 KB Output is correct
18 Correct 437 ms 126688 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 126688 KB Output is correct
2 Correct 3 ms 126688 KB Output is correct
3 Correct 4 ms 126688 KB Output is correct
4 Correct 12 ms 126688 KB Output is correct
5 Correct 9 ms 126688 KB Output is correct
6 Correct 8 ms 126688 KB Output is correct
7 Correct 2 ms 126688 KB Output is correct
8 Correct 138 ms 126688 KB Output is correct
9 Correct 269 ms 126792 KB Output is correct
10 Correct 958 ms 146420 KB Output is correct
11 Correct 433 ms 156620 KB Output is correct
12 Correct 550 ms 165116 KB Output is correct
13 Correct 2 ms 165116 KB Output is correct
14 Correct 142 ms 165116 KB Output is correct
15 Correct 59 ms 165116 KB Output is correct
16 Correct 1103 ms 181232 KB Output is correct
17 Correct 437 ms 190228 KB Output is correct
18 Correct 448 ms 199292 KB Output is correct
19 Runtime error 1206 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 -