# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
90387 |
2018-12-21T13:10:23 Z |
Retro3014 |
Wall (IOI14_wall) |
C++17 |
|
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++){
~^~~~~~~~~~~
# |
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 |
# |
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 |
# |
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 |
# |
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 |
- |