#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, bool flip, int ind, int ss, int se, int si) {
if (spot > se || spot < ss) return;
if (ss == se) {
if (flip) {
seg[si][ind] = val[ss];
}
else {
seg[si][ind] = -1;
}
return;
}
int mid = (ss+se)/2;
// seg[si][ind] += diff; //you know it is in this range
if (spot <= mid) {
upm(spot, flip, ind, ss, mid, si*2+1);
}
else {
upm(spot, flip, ind, mid+1, se, si*2+2);
}
if (ind == 1) {
seg[si][ind] = max(seg[si*2+1][ind], seg[si*2+2][ind]);
}
else {
seg[si][ind] = seg[si*2+1][ind];
if (seg[si][ind] == -1 || seg[si*2+2][ind] != -1 && seg[si*2+2][ind] < seg[si][ind]) {
seg[si][ind] = seg[si*2+2][ind];
}
}
}
void updatem(int spot, bool flip, int ind) {
upm(spot, flip, 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] = spot;
}
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) { //set to non nothing happens thing
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] != -1 && seg[si*2+2][2] <= lval) {
//there is a min in the right side that affects me
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] != -1 && seg[si*2+2][1] >= lval) {
//there is a max in the right side
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;
//precautionary setting and such
for (int i = 0; i < maxk*4; i++) {
seg[i][0] = -1;
seg[i][1] = -1;
seg[i][2] = -1;
}
type[0] = 1;
val[0] = 0;
update(0, true); // i think this is good
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, true, type[v]);
update(v, true);
}
for (int j = 0; j < deactivate[i].size(); j++) {
int v = deactivate[i][j];
updatem(v, false, type[v]);
update(v, false);
}
//do some stuff above this
finalHeight[i] = val[seg[0][0]];
}
return;
}
Compilation message
wall.cpp: In function 'void upm(int, bool, int, int, int, int)':
wall.cpp:47:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (seg[si][ind] == -1 || seg[si*2+2][ind] != -1 && seg[si*2+2][ind] < seg[si][ind]) {
~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < activate[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < deactivate[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
122 ms |
117752 KB |
Output is correct |
| 2 |
Correct |
116 ms |
118004 KB |
Output is correct |
| 3 |
Incorrect |
115 ms |
118004 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
118004 KB |
Output is correct |
| 2 |
Correct |
567 ms |
133716 KB |
Output is correct |
| 3 |
Incorrect |
572 ms |
133716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
133716 KB |
Output is correct |
| 2 |
Correct |
123 ms |
133716 KB |
Output is correct |
| 3 |
Incorrect |
105 ms |
133716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
115 ms |
133716 KB |
Output is correct |
| 2 |
Correct |
100 ms |
133716 KB |
Output is correct |
| 3 |
Incorrect |
102 ms |
133716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
