Submission #403383

#	Time	Username	Problem	Language	Result	Execution time	Memory
403383		jamezzz	조개 줍기 (KOI17_shell)	C++14	0 / 100	255 ms	53168 KiB

shell

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

#define maxn 1500*1500

int cnt=1;
int n,a[1505][1505],lc[maxn+5],rc[maxn+5],sz[maxn+5],lz[maxn+5];
ll s,v[maxn+5];
char t,r,c;

int get(int x,int y){
	return x*n+y;
}

void propo(int id){
	v[id]+=lz[id];
	if(lc[id]!=-1)lz[lc[id]]+=lz[id];
	if(rc[id]!=-1)lz[rc[id]]+=lz[id];
	lz[id]=0;
}

ll val(int id){
	propo(id);
	return v[id];
}

void add(int id,int u){
	lz[id]+=u;
}

void getsize(int id){
	sz[id]=1;
	if(lc[id]!=-1){
		getsize(lc[id]);
		sz[id]+=sz[lc[id]];
	}
	if(rc[id]!=-1){
		getsize(rc[id]);
		sz[id]+=sz[rc[id]];
	}
}

void print(){
	printf("v:\n");
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			printf("%lld ",val(get(i,j)));
		}
		printf("\n");
	}
	printf("sz:\n");
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			printf("%d ",sz[get(i,j)]);
		}
		printf("\n");
	}
	printf("l:\n");
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			printf("%d ",lc[get(i,j)]);
		}
		printf("\n");
	}
	printf("r:\n");
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			printf("%d ",rc[get(i,j)]);
		}
		printf("\n");
	}
}

int main(){
	sf("%d",&n);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			sf("%d",&a[i][j]);
		}
	}
	memset(lc,-1,sizeof lc);
	memset(rc,-1,sizeof rc);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(j==0||v[get(i-1,j)]>v[get(i,j-1)]){
				if(i==0){
					v[get(i,j)]=a[i][j];
					continue;
				}
				lc[get(i-1,j)]=get(i,j);
				v[get(i,j)]=v[get(i-1,j)]+a[i][j];
			}
			else{
				rc[get(i,j-1)]=get(i,j);
				v[get(i,j)]=v[get(i,j-1)]+a[i][j];
			}
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			s+=v[get(i,j)];
		}
	}
	printf("%lld\n",s);
	getsize(0);
	#ifdef DEBUG
	print();
	#endif
	for(int i=0;i<n;++i){
		scanf(" %c",&t);
		scanf("%d%d",&r,&c);
		--r;--c;
		if(t=='U'){
			if(r!=n-1&&c!=0){
				if(val(get(r,c))==val(get(r+1,c-1))&&rc[get(r+1,c-1)]==get(r+1,c)){
					sz[get(r+1,c-1)]-=sz[get(r+1,c)];
					sz[get(r,c)]+=sz[get(r+1,c)];
					rc[get(r+1,c-1)]=-1;
					lc[get(r,c)]=get(r+1,c);
				}
			}
			if(r!=0&&c!=n-1){
				if(val(get(r,c))==val(get(r-1,c+1))&&lc[get(r-1,c+1)]==get(r,c+1)){
					sz[get(r-1,c+1)]-=sz[get(r,c+1)];
					sz[get(r,c)]+=sz[get(r,c+1)];
					lc[get(r-1,c+1)]=-1;
					rc[get(r,c)]=get(r,c+1);
				}
			}
			add(get(r,c),1);
			s+=sz[get(r,c)];
		}
		else{
			if(r!=n-1&&c!=0){
				if(val(get(r,c))==val(get(r+1,c-1))&&lc[get(r,c)]==get(r+1,c)){
					sz[get(r+1,c-1)]+=sz[get(r+1,c)];
					sz[get(r,c)]-=sz[get(r+1,c)];
					rc[get(r+1,c-1)]=get(r+1,c);
					lc[get(r,c)]=-1;
				}
			}
			if(r!=0&&c!=n-1){
				if(val(get(r,c))==val(get(r-1,c+1))&&rc[get(r,c)]==get(r,c+1)){
					sz[get(r-1,c+1)]+=sz[get(r,c+1)];
					sz[get(r,c)]-=sz[get(r,c+1)];
					lc[get(r-1,c+1)]=get(r,c+1);
					rc[get(r,c)]=-1;
				}
			}
			add(get(r,c),-1);
			s-=sz[get(r,c)];
		}
		pf("%lld\n",s);
		#ifdef DEBUG
		print();
		#endif
	}
}

/*
3
3 1 1
1 1 1
1 1 1
U 2 1
U 1 2
U 1 2
*/

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:148:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'char*' [-Wformat=]
  148 |   scanf("%d%d",&r,&c);
      |          ~^    ~~
      |           |    |
      |           int* char*
      |          %hhd
shell.cpp:148:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'char*' [-Wformat=]
  148 |   scanf("%d%d",&r,&c);
      |            ~^     ~~
      |             |     |
      |             int*  char*
      |            %hhd
shell.cpp:112:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  sf("%d",&n);
      |    ^
shell.cpp:115:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |    sf("%d",&a[i][j]);
      |      ^
shell.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf(" %c",&t);
      |   ~~~~~^~~~~~~~~~
shell.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d%d",&r,&c);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54