oj.uz

Submission #129681

# Submission time Handle Problem Language Result Execution time Memory
129681 2019-07-13T03:35:58 Z jhnah917 None (KOI17_shell) C++14
100 / 100
 604 ms 44696 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

struct BIT{
	ll tree[1515];
	
	void update(int l, int r, int v){
		for(; l<=n; l+=l&-l) tree[l] += v;
		for(r++; r<=n; r+=r&-r) tree[r] -= v;
	}
	
	ll query(int x){
		ll ret = 0;
		for(; x; x^=x&-x) ret += tree[x];
		return ret;
	}
} tree[1515];

int arr[1515][1515];
int dp[1515][1515];
ll ans = 0;
int s[1515], e[1515];

inline ll get(int i, int j){
	return dp[i][j] + tree[i].query(j);
}

void getDP(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
			ans += dp[i][j];
		}
	}
}

void query(int a, int b, int c){
	s[a] = e[a] = b;
	for(int i=a+1; i<=n; i++) s[i] = n+1, e[i] = 0;
	
	for(int i=a, j=b;;){
		if(j < n && max(get(i-1, j+1), get(i, j)) + c == max(get(i-1, j+1), get(i, j) + c)) j++;
		else i++;
		if(i > n) break;
		e[i] = j;
	}
	for(int i=a, j=b;;){
		if(i < n && max(get(i+1, j-1), get(i, j)) + c == max(get(i+1, j-1), get(i, j) + c)) i++;
		else j++;
		if(j > n || e[i] < j) break;
		s[i] = min(s[i], j);
	}
	
	for(int i=a; i<=n; i++){
		if(s[i] > e[i]) continue;
		tree[i].update(s[i], e[i], c);
		ans += c * (e[i] - s[i] + 1);
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> arr[i][j];
		}
	}
	getDP();
	cout << ans << "\n";
	
	for(int i=1; i<=n; i++){
		int a, b; char op;
		cin >> op >> a >> b;
		if(op == 'U') query(a, b, 1);
		else query(a, b, -1);
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1628 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1656 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 5 ms 1656 KB Output is correct
6 Correct 5 ms 1656 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 4 ms 1656 KB Output is correct
10 Correct 4 ms 1656 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 20936 KB Output is correct
2 Correct 193 ms 25316 KB Output is correct
3 Correct 236 ms 40440 KB Output is correct
4 Correct 248 ms 24712 KB Output is correct
5 Correct 243 ms 24696 KB Output is correct
6 Correct 195 ms 25316 KB Output is correct
7 Correct 196 ms 25256 KB Output is correct
8 Correct 243 ms 24920 KB Output is correct
9 Correct 242 ms 24884 KB Output is correct
10 Correct 240 ms 24628 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1628 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1656 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 5 ms 1656 KB Output is correct
6 Correct 5 ms 1656 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 4 ms 1656 KB Output is correct
10 Correct 206 ms 20936 KB Output is correct
11 Correct 193 ms 25316 KB Output is correct
12 Correct 236 ms 40440 KB Output is correct
13 Correct 248 ms 24712 KB Output is correct
14 Correct 243 ms 24696 KB Output is correct
15 Correct 195 ms 25316 KB Output is correct
16 Correct 196 ms 25256 KB Output is correct
17 Correct 243 ms 24920 KB Output is correct
18 Correct 242 ms 24884 KB Output is correct
19 Correct 240 ms 24628 KB Output is correct
20 Correct 310 ms 44432 KB Output is correct
21 Correct 313 ms 44560 KB Output is correct
22 Correct 310 ms 44408 KB Output is correct
23 Correct 588 ms 44576 KB Output is correct
24 Correct 558 ms 44696 KB Output is correct
25 Correct 570 ms 44688 KB Output is correct
26 Correct 193 ms 25208 KB Output is correct
27 Correct 227 ms 40400 KB Output is correct
28 Correct 310 ms 44496 KB Output is correct
29 Correct 307 ms 44408 KB Output is correct
30 Correct 568 ms 44668 KB Output is correct
31 Correct 604 ms 44596 KB Output is correct
32 Correct 192 ms 25208 KB Output is correct
33 Correct 259 ms 24724 KB Output is correct
34 Correct 4 ms 1656 KB Output is correct