| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403383 |
2021-05-13T06:18:14 Z |
jamezzz |
None (KOI17_shell) |
C++14 |
|
255 ms |
53168 KB |
#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
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);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
18380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
53168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
18380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
