Submission #18889820


Source Code Expand

Copy
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define rg register
inline long long read(){
	rg long long x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=2e5+5;
int n,m,k;
std::vector<int> h[maxn],l[maxn];
long long ans;
struct asd{
	int l,r,sum;
}tr[maxn<<2];
void push_up(rg int da){
	tr[da].sum=tr[da<<1].sum+tr[da<<1|1].sum;
}
void build(rg int da,rg int l,rg int r){
	tr[da].l=l,tr[da].r=r;
	if(tr[da].l==tr[da].r) return;
	rg int mids=(l+r)>>1;
	build(da<<1,l,mids);
	build(da<<1|1,mids+1,r);
}
void xg(rg int da,rg int wz){
	if(tr[da].l==tr[da].r){
		tr[da].sum=1;
		return;
	}
	rg int mids=(tr[da].l+tr[da].r)>>1;
	if(wz<=mids) xg(da<<1,wz);
	else xg(da<<1|1,wz);
	push_up(da);
}
int cx(rg int da,rg int l,rg int r){
	if(tr[da].l>=l && tr[da].r<=r) return tr[da].sum;
	rg int mids=(tr[da].l+tr[da].r)>>1,nans=0;
	if(l<=mids) nans+=cx(da<<1,l,r);
	if(r>mids) nans+=cx(da<<1|1,l,r);
	return nans;
}
int main(){
	n=read(),m=read(),k=read();
	build(1,1,m);
	rg int aa,bb;
	for(rg int i=1;i<=k;i++){
		aa=read(),bb=read();
		h[aa].push_back(bb);
		l[bb].push_back(aa);
	}
	for(rg int i=1;i<=n;i++){
		std::sort(h[i].begin(),h[i].end());
	}
	for(rg int i=1;i<=m;i++){
		std::sort(l[i].begin(),l[i].end());
	}
	for(rg int i=1;i<=n;i++){
		if(h[i].size()==0) ans+=m;
		else ans+=h[i][0]-1;
		if(h[i].size() && h[i][0]==1) break;
	}
	for(rg int i=1;i<=m;i++){
		if(l[i].size()==0) ans+=n;
		else ans+=l[i][0]-1;
		if(l[i].size() && l[i][0]==1) break;
	}
	rg int ak;
	if(h[1].size()){
		for(rg int i=h[1][0];i<=m;i++){
			xg(1,i);
		}
	}
	for(rg int i=1;i<=n;i++){
		if(h[i].size() && h[i][0]==1) break;
		if(h[i].size()==0) ans-=(m-cx(1,1,m));
		else {
			for(rg int j=0;j<h[i].size();j++){
				xg(1,h[i][j]);
			}
			if(h[i][0]!=1) ans-=(h[i][0]-1-cx(1,1,h[i][0]-1));
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task F - Rook on Grid
User hzoiliuchang
Language C++ (GCC 9.2.1)
Score 600
Code Size 2105 Byte
Status AC
Exec Time 193 ms
Memory 26576 KB

Compile Error

./Main.cpp: In function ‘long long int read()’:
./Main.cpp:8:15: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    8 |  rg long long x=0,fh=1;
      |               ^
./Main.cpp:8:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    8 |  rg long long x=0,fh=1;
      |                   ^~
./Main.cpp:9:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    9 |  rg char ch=getchar();
      |          ^~
./Main.cpp: At global scope:
./Main.cpp:27:21: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   27 | void push_up(rg int da){
      |                     ^~
./Main.cpp:30:19: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   30 | void build(rg int da,rg int l,rg int r){
      |                   ^~
./Main.cpp:30:29: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   30 | void build(rg int da,rg int l,rg int r){
      |                             ^
./Main.cpp:30:38: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   30 | void build(rg int da,rg int l,rg int r){
      |                                      ^
./Main.cpp: In function ‘void build(int, int, int)’:
./Main.cpp:33:9: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   33 |  rg int mids=(l+r)>>1;
      |         ^~~~
./Main.cpp: At global scope:
./Main.cpp:37:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   37 | void xg(rg int da,rg int wz){
      |                ^~
./Main.cpp:37:26: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   37 | void xg(rg int da,rg int wz){
      |                          ^~
./Main.cpp: In function ‘void xg(int, int)’:
./Main.cpp:42:9: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   42 |  r...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 29
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 18 ms 18488 KB
hand_02.txt AC 20 ms 18532 KB
hand_03.txt AC 46 ms 18488 KB
hand_04.txt AC 12 ms 12480 KB
hand_05.txt AC 12 ms 12432 KB
hand_06.txt AC 15 ms 12432 KB
random_01.txt AC 170 ms 26576 KB
random_02.txt AC 120 ms 26496 KB
random_03.txt AC 193 ms 26416 KB
random_04.txt AC 167 ms 26392 KB
random_05.txt AC 102 ms 26416 KB
random_06.txt AC 183 ms 26508 KB
random_07.txt AC 181 ms 26528 KB
random_08.txt AC 23 ms 18652 KB
random_09.txt AC 19 ms 18624 KB
random_10.txt AC 18 ms 18528 KB
random_11.txt AC 37 ms 14400 KB
random_12.txt AC 35 ms 14504 KB
random_13.txt AC 38 ms 14404 KB
random_14.txt AC 38 ms 14568 KB
random_15.txt AC 35 ms 14568 KB
random_16.txt AC 37 ms 14468 KB
random_17.txt AC 32 ms 14448 KB
random_18.txt AC 13 ms 12484 KB
random_19.txt AC 13 ms 12396 KB
random_20.txt AC 16 ms 12528 KB
sample_01.txt AC 15 ms 12432 KB
sample_02.txt AC 16 ms 12396 KB
sample_03.txt AC 18 ms 18576 KB