Submission #958308

# Submission time Handle Problem Language Result Execution time Memory
958308 2024-04-05T11:17:27 Z hocln Wall (IOI14_wall) C++17
0 / 100
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 -