oj.uz

Submission #581700

# Submission time Handle Problem Language Result Execution time Memory
581700 2022-06-23T04:10:03 Z pure_mem Pyramid Base (IOI08_pyramid_base) C++14
65 / 100
 1046 ms 112616 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47280 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47284 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47328 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47816 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51408 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 80220 KB Output is correct
2 Correct 65 ms 80204 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 80124 KB Output is correct
2 Correct 63 ms 80200 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 48160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 52552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 82040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 82396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 82836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 97288 KB Output is correct
2 Correct 293 ms 62868 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 105084 KB Output is correct
2 Correct 712 ms 101224 KB Output is correct
3 Correct 448 ms 94412 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 112616 KB Output is correct
2 Correct 1026 ms 110140 KB Output is correct
3 Correct 1046 ms 109968 KB Output is correct
4 Correct 936 ms 107896 KB Output is correct
5 Correct 728 ms 102660 KB Output is correct