oj.uz

Submission #958358

# Submission time Handle Problem Language Result Execution time Memory
958358 2024-04-05T14:19:01 Z hocln Wall (IOI14_wall) C++17
100 / 100
 944 ms 102616 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
#include "wall.h"
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> 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 ll inf = 2e9;
const ll MN = 3e5 + 15;
const ll 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 ll dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const ll 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;
}
ll tc = 0;
// I hate cp
const long long NO_OPERATION = ~LLONG_MAX;
const long long TYPE = INT_MAX*4LL;
struct item{
	ll mn, mx;
	void apply(ll add, ll l) {
		if(add == NO_OPERATION) return;
		if(add < TYPE) {
			chmax(mx,add);
			chmax(mn,add);
		}
		else {
			chmin(mn,add-TYPE);
			chmin(mx,add-TYPE);
		}
	}
	item operator+(item a) {
		return item();
	}
};

struct segmtree {
	ll 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(ll x) {
		values[x]=merge(values[2*x+1],values[2*x+2]);
	}
	
	void push(ll x, ll lx, ll rx) {
		if(rx - lx == 1) return;
		for(int j : {0,1}) {
			chmax(values[2*x+1+j].mx,values[x].mx);
			chmax(values[2*x+1+j].mn,values[x].mx);
			chmin(values[2*x+1+j].mx,values[x].mn);
			chmin(values[2*x+1+j].mn,values[x].mn);
		}
		values[x].mx = 0;
		values[x].mn = inf;
	}

	void init(ll n) {
		size = 1;
		while (size < n) size *= 2;
		values.resize(size * 2);
	}

	void build(vector<ll>& v, ll x, ll lx, ll rx) {
		if (rx - lx == 1) {
			if (lx < (ll)v.size()) {
				values[x] = single(v[lx]);
			}
			return;
		}
		ll m = (lx + rx) / 2;
		build(v, 2 * x + 1, lx, m);
		build(v, 2 * x + 2, m, rx);
		pull(x);
	}

	void build(vector<ll>& v) {
		build(v, 0, 0, size);
	}

	void set(ll i, ll v, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if (rx - lx == 1) {
			values[x] = single(v);
			return;
		}
		ll 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(ll i, ll v) {
		set(i, v, 0, 0, size);
	}
	
	ll solve(ll i, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if(rx - lx == 1) {
			return values[x].mn;
		}
		ll m = (lx + rx) / 2;
		if(i < m) return solve(i,2*x+1,lx,m);
		else return solve(i,2*x+2,m,rx);
	}
	
	ll solve(ll i) {
		return solve(i,0,0,size);
	}

	item calc(ll l, ll r, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if (lx >= r || rx <= l) return NEUTRAL_ELEMENT;
		if (lx >= l && rx <= r) return values[x];
		ll 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(ll l, ll r) {
		return calc(l, r, 0, 0, size);
	}
	
	void add(ll l, ll r, ll v, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if(lx >= r || rx <= l) return;
		if(lx >= l && rx <= r) {
			values[x].apply(v,rx-lx);
			return;
		}
		ll m = (lx + rx) / 2;
		add(l,r,v,2*x+1,lx,m);
		add(l,r,v,2*x+2,m,rx);
	}
	
	void add(ll l, ll r, ll v) {
		add(l,r,v,0,0,size);
	}
};
segmtree sg;
void update(ll l, ll r, ll 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+5);
	for(ll i = 0;i < k;i++) {
		if(op[i] == 1) {
			update(left[i],right[i],height[i]);
		}
		else {
			update(left[i],right[i],TYPE+(ll)height[i]);
		}
	}
	for(ll i = 0;i < n;i++) finalHeight[i] = sg.solve(i);
}

//inline void solve_test() {
	//sg.init(10);
	//update(1,8,4);
	//update(4,9,1+TYPE);
	//update(3,6,5+TYPE);
	//update(0,5,3);
	//update(2,2,5);
	//update(6,7,0+TYPE);
	//ll n = 10;
	//for(int i = 0;i < sg.values.size();i++) {
		//debug()<<imie(i)imie(sg.values[i].mn)imie(sg.values[i].mx);
	//}
	//vector<ll>ans(n);
	//for(ll 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);
    //ll t = 1;
    ////cin >> t;
    //while(t--) {
		//++tc;
        //solve_test();
    //}
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 10 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 128 ms 13996 KB Output is correct
3 Correct 202 ms 7312 KB Output is correct
4 Correct 576 ms 22520 KB Output is correct
5 Correct 280 ms 23380 KB Output is correct
6 Correct 283 ms 22096 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 129 ms 13944 KB Output is correct
9 Correct 200 ms 8608 KB Output is correct
10 Correct 573 ms 22500 KB Output is correct
11 Correct 300 ms 23376 KB Output is correct
12 Correct 274 ms 21900 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 157 ms 14016 KB Output is correct
15 Correct 41 ms 2492 KB Output is correct
16 Correct 722 ms 22756 KB Output is correct
17 Correct 337 ms 22180 KB Output is correct
18 Correct 294 ms 22100 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1156 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 166 ms 14028 KB Output is correct
9 Correct 198 ms 8528 KB Output is correct
10 Correct 559 ms 22608 KB Output is correct
11 Correct 282 ms 23380 KB Output is correct
12 Correct 287 ms 22092 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 132 ms 14076 KB Output is correct
15 Correct 40 ms 2652 KB Output is correct
16 Correct 730 ms 22752 KB Output is correct
17 Correct 298 ms 22260 KB Output is correct
18 Correct 306 ms 22044 KB Output is correct
19 Correct 919 ms 102616 KB Output is correct
20 Correct 906 ms 99924 KB Output is correct
21 Correct 906 ms 102544 KB Output is correct
22 Correct 891 ms 100192 KB Output is correct
23 Correct 883 ms 99924 KB Output is correct
24 Correct 910 ms 99988 KB Output is correct
25 Correct 892 ms 99924 KB Output is correct
26 Correct 911 ms 102404 KB Output is correct
27 Correct 944 ms 102484 KB Output is correct
28 Correct 878 ms 99924 KB Output is correct
29 Correct 892 ms 100292 KB Output is correct
30 Correct 900 ms 99916 KB Output is correct