| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163411 |
2019-11-13T08:03:20 Z |
davitmarg |
Wall (IOI14_wall) |
C++17 |
|
3000 ms |
18424 KB |
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
#include "wall.h"
#endif
const int N = 2000006;
pair<LL, LL> t[4 * N], d[4 * N];
int col[4 * N], dcol[4 * N];
void build(int v, int l, int r)
{
d[v] = MP(-1, -1);
col[v] = 1;
t[v] = MP(0, 0);
if (l == r)
return;
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
}
void pushColor(int v, int l, int r, int f = 1)
{
if (dcol[v] == 0)
return;
if (l != r)
{
dcol[v * 2] = dcol[v];
dcol[v * 2 + 1] = dcol[v];
if (f)
{
int m = (l + r) / 2;
pushColor(v * 2, l, m, 0);
pushColor(v * 2 + 1, m + 1, r, 0);
}
}
col[v] = dcol[v];
dcol[v] = 0;
}
void paint(int v, int l, int r, int i, int j, int c)
{
pushColor(v, l, r);
if (i > j)
return;
if (l == i && r == j)
{
dcol[v] = c;
pushColor(v, l, r);
return;
}
int m = (l + r) / 2;
paint(v * 2, l, m, i, min(j, m), c);
paint(v * 2 + 1, m + 1, r, max(i, m + 1), j, c);
}
int getCol(int v, int l, int r, int pos)
{
pushColor(v, l, r);
if (l == r)
return col[v];
int m = (l + r) / 2;
if (pos <= m)
return getCol(v * 2, l, m, pos);
else
return getCol(v * 2 + 1, m + 1, r, pos);
}
void addLazy(pair<LL, LL> &a, pair<LL, LL> b)
{
if (b.first != -1)
if (a.first == -1)
a.first = b.first;
else
a.first = max(b.first, a.first);
if (b.second != -1)
if (a.second == -1)
a.second = b.second;
else
a.second = min(b.second, a.second);
}
pair<LL, LL> merge(pair<LL, LL> a, pair<LL, LL> b)
{
a.first = min(a.first, b.first);
a.second = max(a.second, b.second);
return a;
}
void push(int v, int l, int r, int f = 1)
{
if (l != r)
{
addLazy(d[v * 2], d[v]);
addLazy(d[v * 2 + 1], d[v]);
if (f)
{
int m = (l + r) / 2;
push(v * 2, l, m, 0);
push(v * 2 + 1, m + 1, r, 0);
}
}
if (d[v].first != -1)
{
t[v].first = max(t[v].first, d[v].first);
t[v].second = max(t[v].second, t[v].first);
}
if (d[v].second != -1)
{
t[v].second = min(t[v].second, d[v].second);
t[v].first = min(t[v].second, t[v].first);
}
d[v].first = d[v].second = -1;
}
void add(int v, int l, int r, int i, int j, pair<LL, LL> val)
{
push(v, l, r);
if (i > j)
return;
if (l == i && r == j)
{
addLazy(d[v], val);
//cout << d[v].first << " : " << d[v].second << endl;
push(v, l, r);
return;
}
int m = (l + r) / 2;
add(v * 2, l, m, i, min(j, m), val);
add(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
pair<LL, LL> get(int v, int l, int r, int i, int j)
{
push(v, l, r);
if (i > j)
return MP(mod * mod, -mod * mod);
if (l == i && r == j)
return t[v];
int m = (l + r) / 2;
return merge(
get(v * 2, l, m, i, min(j, m)),
get(v * 2 + 1, m + 1, r, max(i, m + 1), j));
}
void buildWall(int n, int k, int op[], int L[], int R[], int H[], int fin[])
{
build(1, 0, n - 1);
for (int i = 0; i < k; i++)
{
if (op[i] == 1)
add(1, 0, n - 1, L[i], R[i], MP(H[i], mod * mod));
else
add(1, 0, n - 1, L[i], R[i], MP(0, H[i]));
paint(1, 0, n - 1, L[i], R[i], op[i]);
}
for (int i = 0; i < n; i++)
{
pair<LL, LL> p = get(1, 0, n - 1, i, i);
//cout << p.first << " : " << p.second << " | " << getCol(1, 0, n - 1, i) << endl;
if (p.first <= p.second)
fin[i] = p.first;
else if (getCol(1, 0, n - 1, i) == 1)
fin[i] = p.first;
else
fin[i] = p.second;
}
}
#ifdef death
int main()
{
int N, K, L[102], R[102], OP[102], H[102], A[102];
cin >> N >> K;
for (int i = 0; i < K; i++)
cin >> OP[i] >> L[i] >> R[i] >> H[i];
buildWall(N, K, OP, L, R, H, A);
for (int i = 0; i < N; i++)
cout << A[i] << endl;
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
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/
Compilation message
wall.cpp: In function 'void addLazy(std::pair<long long int, long long int>&, std::pair<long long int, long long int>)':
wall.cpp:95:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (b.first != -1)
^
wall.cpp:101:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (b.second != -1)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
184 ms |
8180 KB |
Output is correct |
| 3 |
Correct |
890 ms |
6272 KB |
Output is correct |
| 4 |
Execution timed out |
3020 ms |
18424 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
