Contest Duration: ~ (local time) (120 minutes)

Submission #4353112

Source Code Expand

Copy
```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
vector<P2>query[2][2];
vector<int>zax[2][2],zay[2][2];
struct seg{
int seg[(1<<20)];
int v[(1<<20)];
bool f[(1<<20)];
void ini(){
memset(seg,0,sizeof(seg));
memset(v,0,sizeof(v));
memset(f,0,sizeof(f));
}
void init(int i,int x){
v[i+(1<<19)-1] = x;
}
void make(){
for(int i=(1<<19)-2;i>=0;i--){
v[i] = v[i*2+1]+v[i*2+2];
}
}
void lazy(int k){
seg[k*2+1] = v[k*2+1]-seg[k*2+1];
seg[k*2+2] = v[k*2+2]-seg[k*2+2];
f[k*2+1] ^= 1;
f[k*2+2] ^= 1;
f[k] = 0;
}
int update(int a,int b,int k,int l,int r){
if(r<a || b<l) return seg[k];
if(a<=l && r<=b){
seg[k] = v[k]-seg[k];
f[k] ^= 1;
return seg[k];
}
if(f[k]) lazy(k);
return seg[k] = update(a,b,k*2+1,l,(l+r)/2)+update(a,b,k*2+2,(l+r)/2+1,r);
}
int get(){ return seg[0]; }
}t;

map<int,vector<P> >M;
vector<int>z;
ll sol(int a,int b){
t.ini(); z.clear(); M.clear();
//	cout << z.size() << " " << a << " " << b << endl;
for(int i=0;i<query[a][b].size();i++){
z.pb(query[a][b][i].fi.fi-1); z.pb(query[a][b][i].fi.fi);
z.pb(query[a][b][i].fi.sc); z.pb(query[a][b][i].fi.sc+1);
M[query[a][b][i].sc.fi].pb(mp(query[a][b][i].fi.fi,query[a][b][i].fi.sc));
M[query[a][b][i].sc.sc+1].pb(mp(query[a][b][i].fi.fi,query[a][b][i].fi.sc));
}
sort(z.begin(),z.end()); z.erase(unique(z.begin(),z.end()),z.end());
for(int i=0;i<z.size()-1;i++) t.init(i,z[i+1]-z[i]);
t.make();
int pre = 0;
ll ret = 0;
for(map<int,vector<P> >::iterator it = M.begin();it != M.end();it++){
vector<P>&v = it->sc;
ret += 1LL * (it->fi - pre) * t.get(); pre = it->fi;
for(int i=0;i<v.size();i++){
int x = v[i].fi;
int y = v[i].sc;
x = lower_bound(z.begin(),z.end(),x)-z.begin();
y = lower_bound(z.begin(),z.end(),y)-z.begin();
t.update(x,y,0,0,(1<<19)-1);
}
}
return ret;
}
int main(){
scanf("%d",&n);
rep(i,n){
int h,w,r,c; scanf("%d%d%d%d",&r,&c,&h,&w);
rep(x,2)rep(y,2){
if((x+y)%2 == (h+w)%2){
int hh = h;
while(hh%2 != x%2) hh++;
int A = (hh+1)/2;
hh = h+r-1;
while(hh%2 != x%2) hh--;
int B = (hh+1)/2;
hh = w;
while(hh%2 != y%2) hh++;
int C = (hh+1)/2;
hh = w+c-1;
while(hh%2 != y%2) hh--;
int D = (hh+1)/2;
if(A<=B && C<=D){

query[x][y].pb(mp(mp(A,B),mp(C,D)));
//	cout << x << y << A << B << C  << D << endl;
}
}
}
}
ll ans = 0;
rep(x,2)rep(y,2) {if(query[x][y].empty()) continue;ans += sol(x,y);}
cout << ans << endl;
}```

#### Submission Info

Submission Time 2019-02-23 14:45:25+0900 C - Checkered Stamps IH19980412 C++14 (GCC 5.4.1) 800 3154 Byte AC 674 ms 24412 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:91:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:93:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int h,w,r,c; scanf("%d%d%d%d",&r,&c,&h,&w);
^
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
 AC × 2
 AC × 17
Set Name Test Cases
Sample 01.txt, 02.txt
All 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
Case Name Status Exec Time Memory
01.txt 7 ms 9472 KB
02.txt 7 ms 9472 KB
11.txt 5 ms 9472 KB
12.txt 5 ms 9472 KB
13.txt 7 ms 9472 KB
14.txt 7 ms 9472 KB
15.txt 10 ms 9600 KB
16.txt 649 ms 24408 KB
17.txt 669 ms 24348 KB
18.txt 657 ms 24328 KB
19.txt 648 ms 24288 KB
20.txt 646 ms 24328 KB
21.txt 648 ms 24276 KB
22.txt 653 ms 24328 KB
23.txt 649 ms 24284 KB
24.txt 652 ms 24332 KB
25.txt 674 ms 24412 KB