oj.uz

Submission #90387

# Submission time Handle Problem Language Result Execution time Memory
90387 2018-12-21T13:10:23 Z Retro3014 Wall (IOI14_wall) C++17
61 / 100
 1243 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 2 ms 376 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 4 ms 720 KB Output is correct
4 Correct 12 ms 1788 KB Output is correct
5 Correct 9 ms 1916 KB Output is correct
6 Correct 9 ms 2024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2024 KB Output is correct
2 Correct 143 ms 14520 KB Output is correct
3 Correct 280 ms 15756 KB Output is correct
4 Correct 1006 ms 35300 KB Output is correct
5 Correct 440 ms 45376 KB Output is correct
6 Correct 428 ms 54108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54108 KB Output is correct
2 Correct 4 ms 54108 KB Output is correct
3 Correct 4 ms 54108 KB Output is correct
4 Correct 12 ms 54108 KB Output is correct
5 Correct 11 ms 54108 KB Output is correct
6 Correct 9 ms 54108 KB Output is correct
7 Correct 2 ms 54108 KB Output is correct
8 Correct 142 ms 54108 KB Output is correct
9 Correct 272 ms 54176 KB Output is correct
10 Correct 891 ms 73620 KB Output is correct
11 Correct 432 ms 82844 KB Output is correct
12 Correct 414 ms 82880 KB Output is correct
13 Correct 2 ms 82880 KB Output is correct
14 Correct 140 ms 82880 KB Output is correct
15 Correct 58 ms 82880 KB Output is correct
16 Correct 1152 ms 82936 KB Output is correct
17 Correct 438 ms 82936 KB Output is correct
18 Correct 448 ms 83004 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 83004 KB Output is correct
2 Correct 3 ms 83004 KB Output is correct
3 Correct 4 ms 83004 KB Output is correct
4 Correct 11 ms 83004 KB Output is correct
5 Correct 9 ms 83004 KB Output is correct
6 Correct 8 ms 83004 KB Output is correct
7 Correct 2 ms 83004 KB Output is correct
8 Correct 138 ms 83004 KB Output is correct
9 Correct 273 ms 83004 KB Output is correct
10 Correct 963 ms 83004 KB Output is correct
11 Correct 426 ms 83028 KB Output is correct
12 Correct 417 ms 83028 KB Output is correct
13 Correct 2 ms 83028 KB Output is correct
14 Correct 141 ms 83028 KB Output is correct
15 Correct 55 ms 83028 KB Output is correct
16 Correct 1122 ms 83028 KB Output is correct
17 Correct 618 ms 83028 KB Output is correct
18 Correct 447 ms 83028 KB Output is correct
19 Correct 1233 ms 203220 KB Output is correct
20 Correct 1214 ms 211420 KB Output is correct
21 Correct 1231 ms 224132 KB Output is correct
22 Correct 1228 ms 232196 KB Output is correct
23 Correct 1229 ms 242604 KB Output is correct
24 Correct 1213 ms 252264 KB Output is correct
25 Correct 1243 ms 261204 KB Output is correct
26 Runtime error 1233 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.
27 Halted 0 ms 0 KB -