# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
62452 |
2018-07-28T13:55:21 Z |
evpipis |
Wall (IOI14_wall) |
C++11 |
|
0 ms |
0 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define TEST
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int len = 1e5+5, inf = 1e9;
ii tree[4*len];
void upd(ii &a, ii b){
if (a.fi <= b.fi && b.se <= a.se)
a = b;
else if (b.fi < a.fi)
a.se = min(a.se, b.se), a.fi = min(a.fi, b.se);
else if (b.se > a.se)
a.fi = max(a.fi, b.fi), a.se = max(a.se, b.fi);
}
void prop(int p, int l, int r){
if (l == r) return;
upd(tree[2*p], tree[p]);
upd(tree[2*p+1], tree[p]);
tree[p] = mp(0, inf);
}
void update(int p, int l, int r, int i, int j, ii val){
prop(p, l, r);
if (r < i || j < l)
return;
if (i <= l && r <= j)
upd(tree[p], val);
else{
int mid = (l+r)/2;
update(2*p, l, mid, i, j, val);
update(2*p+1, mid+1, r, i, j, val);
}
}
int query(int p, int l, int r, int i){
prop(p, l, r);
if (l == r)
return tree[p].fi;
int mid = (l+r)/2;
if (i <= mid)
return query(2*p, l, mid, i);
return query(2*p+1, mid+1, r, i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < 4*n; i++)
tree[i] = mp(0, inf);
for (int i = 0; i < k; i++){
ii val;
int t = op[i], l = left[i], r = right[i], h = height[i];
if (t == 1)
val = mp(h, inf);
else
val = mp(0, h);
update(1, 0, n-1, l, r, val);
}
for (int i = 0; i < n; i++)
finalHeight[i] = query(1, 0, n-1, i);
return;
}
#ifdef TEST
int main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}
#endif
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
Compilation message
/tmp/ccVtIhuF.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccYqILbd.o:wall.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status