| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52104 |
2018-06-23T23:22:15 Z |
shoemakerjo |
Wall (IOI14_wall) |
C++14 |
|
600 ms |
122612 KB |
#include "wall.h"
#include <cmath>
#include <vector>
using namespace std;
#define maxn 2000010
#define maxk 500010
int seg[maxk*4][3]; //store over the three
//seg[i][0] is for range ops
//seg[i][1] is for number of maxes
//seg[i][2] is for number of mins
//result is always stored in seg[0][0]
//-1 will be used to signify that nothing happens
int N, K;
int type[maxk];
int val[maxk];
vector< vector<int> > activate(maxn);
vector< vector<int> > deactivate(maxn);
void upm(int spot, int diff, int ind, int ss, int se, int si) {
if (spot > se || spot < ss) return;
if (ss == se) {
seg[si][ind] += diff;
return;
}
int mid = (ss+se)/2;
seg[si][ind] += diff; //you know it is in this range
if (spot <= mid) {
upm(spot, diff, ind, ss, mid, si*2+1);
}
else {
upm(spot, diff, ind, mid+1, se, si*2+2);
}
}
void updatem(int spot, int diff, int ind) {
upm(spot, diff, ind, 0, K, 0);
}
void up(int spot, bool flip, int ss, int se, int si) {
if (spot < ss || spot > se) return;
if (ss == se) {
if (flip) {
seg[si][0] = ss;
}
else seg[si][0] = -1;
return;
}
int mid = (ss+se)/2;
if (spot <= mid) up(spot, flip, ss, mid, si*2+1);
else up(spot, flip, mid+1, se, si*2+2);
//now we must merge range
int ole = seg[si*2+1][0];
int ori = seg[si*2+2][0];
if (ole == -1) {
seg[si][0] = ori;
return;
}
if (ori == -1) {
seg[si][0] = ole;
return;
}
int lval = val[ole];
int rval = val[ori];
int lt = type[ole];
int rt = type[ori];
if (rt == 1) {
if (lval <= rval) {
seg[si][0] = ori;
return;
}
if (seg[si*2+2][2] > 0) {
//there is a min in the right chunk
seg[si][0] = ori;
return;
}
seg[si][0] = ole;
return;
}
else { //rt is 2 (a min)
if (lval >= rval) {
seg[si][0] = ori;
return;
}
if (seg[si*2+2][1] > 0) {
//there is a max in the right
seg[si][0] = ori;
return;
}
seg[si][0] = ole;
return;
}
}
void update(int spot, bool flip) {
//flip is true if you turn it on, false if not
//have to reprocess all ranges with this thing in it
up(spot, flip, 0, K, 0);
}
void buildWall(int n, int k, int op[], int left[],
int right[], int height[], int finalHeight[]){
N = n;
K = k;
for (int i = 0; i < maxk; i++) {
seg[i][0] = -1;
seg[i][1] = seg[i][2] = 0;
}
update(0, true); // i think this is good
type[0] = 1;
val[0] = 0;
for (int i = 0; i < k; i++) {
type[i+1] = op[i];
val[i+1] = height[i];
activate[left[i]].push_back(i+1);
deactivate[right[i]+1].push_back(i+1);
}
for (int i = 0; i < n; i++) {
//process things and then fill my finalheight
for (int j = 0; j < activate[i].size(); j++) {
int v = activate[i][j];
updatem(v, 1, type[v]);
update(v, true);
}
for (int j = 0; j < deactivate[i].size(); j++) {
int v = deactivate[i][j];
updatem(v, -1, type[v]);
update(v, false);
}
//do some stuff above this
finalHeight[i] = val[seg[0][0]];
}
return;
}
Compilation message
wall.cpp: In function 'void up(int, bool, int, int, int)':
wall.cpp:68:6: warning: unused variable 'lt' [-Wunused-variable]
int lt = type[ole];
^~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:130:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < activate[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < deactivate[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
100088 KB |
Output is correct |
| 2 |
Correct |
86 ms |
100356 KB |
Output is correct |
| 3 |
Incorrect |
86 ms |
100356 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
100356 KB |
Output is correct |
| 2 |
Correct |
442 ms |
122612 KB |
Output is correct |
| 3 |
Incorrect |
600 ms |
122612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
122612 KB |
Output is correct |
| 2 |
Correct |
96 ms |
122612 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
122612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
122612 KB |
Output is correct |
| 2 |
Correct |
86 ms |
122612 KB |
Output is correct |
| 3 |
Incorrect |
87 ms |
122612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
