Submission #581700

#	Time	Username	Problem	Language	Result	Execution time	Memory
581700		pure_mem	Pyramid Base (IOI08_pyramid_base)	C++14	65 / 100	1046 ms	112616 KiB

pyramid_base

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6 + 2, M = 2e6, LG = 18;
const ll INF = 1e9 + 7, MAX = 1e18, mod = 1e9 + 7;

struct node {
	int tt = 0;
	int dp[3] = {};

	int get(int v) const {
		if(tt > 0)
			return 0;
		return dp[v];
	}

	void pnode(const node& L, const node& R, int tl, int tr) {
		dp[0] = max(max(L.get(0), R.get(0)), L.get(2) + R.get(1));
		dp[1] = L.get(1), dp[2] = R.get(2);
		
		int tm = (tl + tr) / 2;
		if(tm - tl + 1 == dp[1])
			dp[1] += R.get(1);
		if(tr - tm == dp[2])
			dp[2] += L.get(2);
	}

} t[N * 4];

void build(int v, int tl, int tr) {
	t[v].tt = 0;
	if(tl == tr) {
		t[v] = {0, {1, 1, 1}};
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm + 1, tr);
	t[v].pnode(t[v * 2], t[v * 2 + 1], tl, tr);
}

void upd(int v, int tl, int tr, int l, int r, int val) {
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r) {
		t[v].tt += val;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v].pnode(t[v * 2], t[v * 2 + 1], tl, tr);
}

int m, n, B, q;
vector< array<int, 2> > todo[N], todo_d[N];

void add(int x, int val) {
	for(auto &cur: todo[x])
		upd(1, 1, n, cur[0], cur[1], val);
}

void del(int x, int val) {
	for(auto &cur: todo_d[x])
		upd(1, 1, n, cur[0], cur[1], val);
}

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;
    cin >> B;
    cin >> q;
    
    for(int i = 1;i <= q;i++) {
    	int x1, y1, x2, y2, c;
    	cin >> x1 >> y1 >> x2 >> y2 >> c;
    
    	todo[x1].push_back({y1, y2});
    	todo_d[x2].push_back({y1, y2});
    }
    build(1, 1, n);
    int res = 0;
    for(int x1 = 1, x2 = 0;x1 <= m;) {
    	while(x2 <= m && x2 - x1 + 1 <= t[1].get(0))
    		add(++x2, 1);
    	//cerr << x1 << " " << x2 << " " << t[1].get(0) << "\n";
    	res = max(res, x2 - x1);
    	del(x1++, -1);
    }

    cout << res;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10