oj.uz

Submission #404099

# Submission time Handle Problem Language Result Execution time Memory
404099 2021-05-13T18:44:45 Z errorgorn None (KOI17_shell) C++17
46 / 100
 2000 ms 230728 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) val+=k;
		else if (j<=m) l->update(i,j,k);
		else if (m<i) r->update(i,j,k);
		else l->update(i,m,k),r->update(m+1,j,k);
	}
	
	int query(int i){
		if (s==e) return val;
		else if (i<=m) return val+l->query(i);
		else return val+r->query(i);
	}
} *root[1505];

int n;
int arr[1505][1505];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,1,n+1) rep(y,1,n+1) cin>>arr[x][y];
	
	rep(x,0,1505) root[x]=new node(0,1505);
	
	ll ans=0;
	rep(x,1,n+1) rep(y,1,n+1){
		int temp=max(root[x]->query(y-1),root[x-1]->query(y))+arr[x][y];
		root[x]->update(y,y,temp);
		ans+=temp;
	}
	
	cout<<ans<<endl;
	
	char c;
	int a,b;
	
	rep(x,0,n){
		cin>>c>>a>>b;
		
		if (c=='U'){
			arr[a][b]++;
			
			int l=b,r=b;
			rep(y,a,n+1){
				while (r!=n && root[y]->query(r)+arr[y][r+1]==root[y]->query(r+1)){
					r++;
				}
				while (l<=r && root[y]->query(l)==
					max(root[y-1]->query(l),root[y]->query(l-1))+arr[y][l]){
						
					l++;
				}
				if (r<l) break;
				
				root[y]->update(l,r,1);
				ans+=(r-l+1);
			}
		}
		else{
			arr[a][b]--;
			
			int l=b,r=b;
			rep(y,a,n+1){
				while (r!=n && root[y-1]->query(r+1)+arr[y][r+1]!=root[y]->query(r+1)){
					r++;
				}
				while (l<=r && root[y]->query(l)==
					max(root[y-1]->query(l),root[y]->query(l-1))+arr[y][l]){
						
					l++;
				}
				
				if (r<l) break;
				root[y]->update(l,r,-1);
				ans-=(r-l+1);
			}
		}
		
		cout<<ans<<endl;
	}
}

Compilation message

shell.cpp: In constructor 'node::node(int, int)':
shell.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 213548 KB Output is correct
2 Correct 234 ms 213548 KB Output is correct
3 Correct 213 ms 213624 KB Output is correct
4 Correct 225 ms 213592 KB Output is correct
5 Correct 215 ms 213568 KB Output is correct
6 Correct 228 ms 213576 KB Output is correct
7 Correct 213 ms 213612 KB Output is correct
8 Correct 213 ms 213540 KB Output is correct
9 Correct 212 ms 213572 KB Output is correct
10 Correct 222 ms 213728 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 221984 KB Output is correct
2 Correct 648 ms 222020 KB Output is correct
3 Correct 692 ms 222088 KB Output is correct
4 Correct 614 ms 221972 KB Output is correct
5 Correct 616 ms 221984 KB Output is correct
6 Correct 656 ms 221980 KB Output is correct
7 Correct 651 ms 221996 KB Output is correct
8 Correct 620 ms 221992 KB Output is correct
9 Correct 666 ms 222000 KB Output is correct
10 Correct 636 ms 221892 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 213548 KB Output is correct
2 Correct 234 ms 213548 KB Output is correct
3 Correct 213 ms 213624 KB Output is correct
4 Correct 225 ms 213592 KB Output is correct
5 Correct 215 ms 213568 KB Output is correct
6 Correct 228 ms 213576 KB Output is correct
7 Correct 213 ms 213612 KB Output is correct
8 Correct 213 ms 213540 KB Output is correct
9 Correct 212 ms 213572 KB Output is correct
10 Correct 677 ms 221984 KB Output is correct
11 Correct 648 ms 222020 KB Output is correct
12 Correct 692 ms 222088 KB Output is correct
13 Correct 614 ms 221972 KB Output is correct
14 Correct 616 ms 221984 KB Output is correct
15 Correct 656 ms 221980 KB Output is correct
16 Correct 651 ms 221996 KB Output is correct
17 Correct 620 ms 221992 KB Output is correct
18 Correct 666 ms 222000 KB Output is correct
19 Correct 636 ms 221892 KB Output is correct
20 Correct 222 ms 213728 KB Output is correct
21 Correct 709 ms 230556 KB Output is correct
22 Correct 721 ms 230528 KB Output is correct
23 Correct 745 ms 230476 KB Output is correct
24 Execution timed out 2058 ms 230728 KB Time limit exceeded
25 Halted 0 ms 0 KB -