| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 17239 |
2015-11-09T18:12:53 Z |
erdemkiraz |
Wall (IOI14_wall) |
C++ |
|
31 ms |
103284 KB |
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define sol (root + root)
#define sag (root + root + 1)
#define orta ((bas + son) >> 1)
#define bit __builtin_popcount
#ifndef D
#define dbg(x) 0
#define dbgs(x) 0
#else
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#endif
typedef long long ll;
typedef pair < int, int > pii;
const int inf = 1e9 + 5;
const ll linf = 1e18 + 5;
const int N = 2000000 + 5;
class node{
public:
int l, r, w;
node() {
l = r = -1;
w = 0;
}
};
int n, m, type, x, y, k, a[N];
node kd[N << 2];
node make(int l, int r, int w) {
node t;
t.l = l;
t.r = r;
t.w = w;
return t;
}
node max_here(int root, int k) {
if(kd[root].r == -1) {
if(kd[root].l != -1 and k < kd[root].l)
return kd[root];
return kd[root] = make(k, -1, 0);
}
if(kd[root].l == -1)
return kd[root] = make(k, max(k, kd[root].r), 0);
return kd[root] = make(max(k, kd[root].l), max(kd[root].r, max(k, kd[root].l)), 0);
}
node min_here(int root, int k) {
if(kd[root].l == -1) {
if(kd[root].r != -1 and k > kd[root].r)
return kd[root];
return kd[root] = make(-1, k, 1);
}
if(kd[root].r == -1)
return kd[root] = make(min(k, kd[root].l), k, 1);
return kd[root] = make(min(kd[root].l, min(k, kd[root].r)), min(k, kd[root].r), 1);
}
void push(int root) {
if(kd[root].w == 0) {
if(kd[root].r != -1) {
min_here(sol, kd[root].r);
min_here(sag, kd[root].r);
}
if(kd[root].l != -1) {
max_here(sol, kd[root].l);
max_here(sag, kd[root].l);
}
}
else {
if(kd[root].l != -1) {
max_here(sol, kd[root].l);
max_here(sag, kd[root].l);
}
if(kd[root].r != -1) {
min_here(sol, kd[root].r);
min_here(sag, kd[root].r);
}
}
kd[root].l = -1;
kd[root].r = -1;
kd[root].w = 0;
}
void upmax(int root, int bas, int son, int x, int y, int k) {
if(son < x or y < bas)
return;
if(x <= bas and son <= y) {
max_here(root, k);
return;
}
push(root);
upmax(sol, bas, orta, x, y, k);
upmax(sag, orta + 1, son, x, y, k);
}
void upmin(int root, int bas, int son, int x, int y, int k) {
if(son < x or y < bas)
return;
if(x <= bas and son <= y) {
min_here(root, k);
return;
}
push(root);
upmin(sol, bas, orta, x, y, k);
upmin(sag, orta + 1, son, x, y, k);
}
void calc(int root, int bas, int son) {
if(bas == son) {
a[bas] = kd[root].l;
return;
}
push(root);
calc(sol, bas, orta);
calc(sag, orta + 1, son);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
:: n = n;
:: m = m;
for(int i = 0; i < m; i++) {
int type = op[i];
int x = left[i] + 1;
int y = right[i] + 1;
int k = height[i];
if(type == 1)
upmax(1, 1, n, x, y, k);
else
upmin(1, 1, n, x, y, k);
}
calc(1, 1, n);
FOR(i, 1, n) {
if(a[i] == -1)
a[i] = 0;
finalHeight[i - 1] = a[i];
}
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
103284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
103284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
103284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
103284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
