| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 600141 |
2022-07-20T13:33:24 Z |
snokes |
Wall (IOI14_wall) |
C++17 |
|
868 ms |
24208 KB |
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL
#define vt vector
const int INF = 1e9 + 5;
struct Op
{
int mn, mx, mode;
Op (int a, int b, int c)
{
mn = a;
mx = b;
mode = c;
}
void apply(const Op other)
{
assert(other.mode == 1 || other.mode == 2);
if(mode == 0)
{
*this = other;
return;
}
if(other.mode == 1)
{
//Min mode
if(mode == 1) mn = min(mn, other.mn);
else mn = min(mx, other.mn);
mx = min(mx, mn);
}
else
{
//Max mode
if(mode == 2) mx = max(mx, other.mx);
else mx = max(other.mx, mn);
mn = max(mn, mx);
}
mode = other.mode;
assert(mn == mx);
}
};
ostream& operator << (ostream& os, Op o)
{
return os << "(mn:" << o.mn << ", mx: " << o.mx << ", mode:" << o.mode << ")";
}
bool operator == (Op a, Op b)
{
return a.mn == b.mn && a.mx == b.mx && a.mode == b.mode;
}
const Op NONE(0, 0, 0);
struct SegTree
{
vector<int> S;
vector<Op> lazy;
int N;
SegTree(int _N)
{
for(N = 1; N < _N; N *= 2);
S = vector<int>(2 * N);
lazy = vector<Op>(2 * N, NONE);
}
void push(int i)
{
if(lazy[i] == NONE) return;
assert(lazy[i].mn == lazy[i].mx);
if(i < N) S[i] = lazy[i].mn;
else
{
if(lazy[i].mode == 1) S[i] = min(S[i], lazy[i].mn);
else S[i] = max(S[i], lazy[i].mx);
}
if(i < N)
{
lazy[2 * i].apply(lazy[i]);
lazy[2 * i + 1].apply(lazy[i]);
}
lazy[i] = NONE;
}
int qry(int l, int r, int a, int b, int i)
{
push(i);
if(l <= a && b <= r) return S[i];
if(b < l || r < a) return 0;
int m = (a + b) / 2;
return qry(l, r, a, m, 2 * i) + qry(l, r, m + 1, b, 2 * i + 1);
}
int qry(int i)
{
assert(1 <= i && i <= N);
return qry(i, i, 1, N, 1);
}
void upd(int l, int r, Op o, int a, int b, int i)
{
push(i);
if(l <= a && b <= r)
{
dbg(o);
lazy[i].apply(o);
dbg(lazy[i]);
push(i);
return;
}
if(r < a || b < l) return;
int m = (a + b) / 2;
upd(l, r, o, a, m, 2 * i);
upd(l, r, o, m + 1, b, 2 * i + 1);
}
void upd(int l, int r, Op o)
{
upd(l, r, o, 1, N, 1);
}
};
void buildWall(int N, int Q, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree s(N);
vector<pair<int, int>> range(2 * s.N);
range[1] = {1, s.N};
for(int i = 1; i < s.N; i++)
{
int m = (range[i].first + range[i].second) / 2;
range[2 * i] = {range[i].first, m};
range[2 * i + 1] = {m + 1, range[i].second};
}
//for(int i = 1; i <= N; i++) s.upd(i, i, Op(0, 0));
for(int i = 0; i < Q; i++)
{
op[i] = op[i] == 1 ? 2 : 1;
Op here(height[i], height[i], op[i]);
//dbg(here);
s.upd(1 + left[i], 1 + right[i], here);
//for(int i = 1; i < 2 * s.N; i++) dbg(i, range[i], s.lazy[i]);
//dbg("here");
}
for(int i = 0; i < N; i++)
{
finalHeight[i] = s.qry(i + 1);
}
}
/*
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;
}
*/
/*
6 2
1 3 4 3
2 3 5 1
*/
/*
10 2
1 3 4 2
2 3 5 1
*/
/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
127 ms |
13900 KB |
Output is correct |
| 3 |
Correct |
274 ms |
8956 KB |
Output is correct |
| 4 |
Incorrect |
868 ms |
24208 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
440 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
