| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 958308 |
2024-04-05T11:17:27 Z |
hocln |
Wall (IOI14_wall) |
C++17 |
|
170 ms |
14080 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
is >> p.first;
return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
for (auto &i: v) os << i << ' ';
return os;
}
int tc = 0;
// I hate cp
const long long NO_OPERATION = ~LLONG_MAX;
struct item{
ll sum = 0, op = 0;
void apply(ll add, ll l) {
if(add == NO_OPERATION) return;
op = add;
if(add >= 0) {
sum = max(sum,add);
}
else {
sum = min(sum,~add);
}
}
item operator+(item a) {
item res;
res.op = NO_OPERATION;
return res;
}
};
struct segmtree {
int size = 1;
vector<item> values;
item NEUTRAL_ELEMENT = { 0, NO_OPERATION};
item single(ll v) {
return {0,v};
}
item merge(item a, item b) {
return a + b;
}
void pull(int x) {
values[x]=merge(values[2*x+1],values[2*x+2]);
}
void push(int x, int lx, int rx) {
if(rx - lx == 1) return;
values[2*x+1].apply(values[x].op,(rx-lx)/2);
values[2*x+2].apply(values[x].op,(rx-lx)/2);
values[x] = merge(values[2*x+1],values[2*x+2]);
pull(x);
}
void init(int n) {
size = 1;
while (size < n) size *= 2;
values.resize(size * 2);
}
void build(vector<int>& v, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < (int)v.size()) {
values[x] = single(v[lx]);
}
return;
}
int m = (lx + rx) / 2;
build(v, 2 * x + 1, lx, m);
build(v, 2 * x + 2, m, rx);
pull(x);
}
void build(vector<int>& v) {
build(v, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx) {
push(x,lx,rx);
if (rx - lx == 1) {
values[x] = single(v);
return;
}
int m = (lx + rx) / 2;
if (i < m) {
set(i, v, 2 * x + 1, lx, m);
}
else set(i, v, 2 * x + 2, m, rx);
pull(x);
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int solve(int i, int x, int lx, int rx) {
push(x,lx,rx);
if(rx - lx == 1) {
return values[x].sum;
}
int m = (lx + rx) / 2;
if(i < m) return solve(i,2*x+1,lx,m);
else return solve(i,2*x+2,m,rx);
pull(x);
}
int solve(int i) {
return solve(i,0,0,size);
}
item calc(int l, int r, int x, int lx, int rx) {
push(x,lx,rx);
if (lx >= r || rx <= l) return NEUTRAL_ELEMENT;
if (lx >= l && rx <= r) return values[x];
int m = (lx + rx) / 2;
item v1 = calc(l, r, 2 * x + 1, lx, m);
item v2 = calc(l, r, 2 * x + 2, m, rx);
return merge(v1, v2);
}
item calc(int l, int r) {
return calc(l, r, 0, 0, size);
}
void add(int l, int r, int v, int x, int lx, int rx) {
push(x,lx,rx);
if(lx >= r || rx <= l) return;
if(lx >= l && rx <= r) {
values[x].apply(v,rx-lx);
return;
}
int m = (lx + rx) / 2;
add(l,r,v,2*x+1,lx,m);
add(l,r,v,2*x+2,m,rx);
pull(x);
}
void add(int l, int r, int v) {
add(l,r,v,0,0,size);
}
};
segmtree sg;
void update(int l, int r, int val) {
++r;
sg.add(l,r,val);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]) {
sg.init(n+2);
for(int i = 0;i < k;i++) {
if(op[i] == 1) {
update(left[i],right[i],height[i]);
}
else {
update(left[i],right[i],~height[i]);
}
}
for(int i = 0;i < n;i++) finalHeight[i] = sg.solve(i);
}
//inline void solve_test() {
//update(1,8,4);
//update(4,9,~1);
//update(3,6,~5);
//update(0,5,3);
//update(2,2,5);
//update(6,7,~0);
//int n = 10;
//vector<int>ans(n);
//for(int i = 0;i < n;i++) {
//ans[i] = sg.solve(i);
//}
//cout << ans;
//}
//int main()
//{
////srand(chrono::steady_clock::now().time_since_epoch().count());
////freopen("convention2.in", "r", stdin);
////freopen("convention2.out", "w", stdout);
////cout << "Case #" << tc << ": " << ans << '\n';
////cout << fixed << setprecision(4);
//ios::sync_with_stdio(0);
//cin.tie(0);cout.tie(0);
//int t = 1;
////cin >> t;
//while(t--) {
//++tc;
//solve_test();
//}
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
119 ms |
14080 KB |
Output is correct |
| 3 |
Incorrect |
170 ms |
7312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
