oj.uz

Submission #154690

# Submission time Handle Problem Language Result Execution time Memory
154690 2019-09-23T13:54:10 Z junodeveloper 허수아비 (JOI14_scarecrows) C++14
100 / 100
 691 ms 69240 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n;
pii p[200010];
vector<pii> tree[4*200010];
void update(int h,int tl,int tr,int x,int y) {
	if(tr<y||y<tl)return;
	while(!tree[h].empty()&&tree[h].back().se<y)
		tree[h].pop_back();
	tree[h].push_back({x,y});
	if(tl==tr)return;
	int mid=(tl+tr)/2;
	update(h*2,tl,mid,x,y);
	update(h*2+1,mid+1,tr,x,y);
}
pii query(int h,int tl,int tr,int l,int r,pii c) {
	if(r<tl||tr<l) return c;
	if(l<=tl&&tr<=r) {
		if(tree[h].empty()) return c;
		int i=lower_bound(all(tree[h]),make_pair(c.fi+1,-1))-tree[h].begin();
		return {max(tree[h].back().fi,c.fi), c.se+sz(tree[h])-i};
	}
	int mid=(tl+tr)/2;
	pii qr=query(h*2+1,mid+1,tr,l,r,c);
	return query(h*2,tl,mid,l,r,qr);
}
int main() {
	scanf("%d",&n);
	int i;
	vector<int> vx,vy;
	for(i=1;i<=n;i++){ 
		scanf("%d%d",&p[i].fi,&p[i].se);
		vx.push_back(p[i].fi);
		vy.push_back(p[i].se);
	}
	sort(all(vx));
	vx.erase(unique(all(vx)),vx.end());
	sort(all(vy));
	vy.erase(unique(all(vy)),vy.end());
	for(i=1;i<=n;i++) {
		p[i].fi=lower_bound(all(vx),p[i].fi)-vx.begin();
		p[i].se=lower_bound(all(vy),p[i].se)-vy.begin();
	}
	sort(p+1,p+n+1,[&](const pii& a,const pii& b) {
		return a.fi==b.fi?a.se>b.se:a.fi<b.fi;
	});
	ll res=0;
	for(i=1;i<=n;i++) {
		pii r=query(1,0,sz(vy),0,p[i].se-1,make_pair(-1,0));
		res+=r.se;
		//printf("(%d,%d):%d\n",vx[p[i].fi],vy[p[i].se],r.se);
		update(1,0,sz(vy),p[i].fi,p[i].se);
	}
	printf("%lld",res);
	return 0;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
scarecrows.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i].fi,&p[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19320 KB Output is correct
2 Correct 21 ms 19192 KB Output is correct
3 Correct 21 ms 19192 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 21 ms 19192 KB Output is correct
6 Correct 21 ms 19192 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct
8 Correct 21 ms 19152 KB Output is correct
9 Correct 21 ms 19192 KB Output is correct
10 Correct 21 ms 19192 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20340 KB Output is correct
2 Correct 30 ms 19704 KB Output is correct
3 Correct 28 ms 19932 KB Output is correct
4 Correct 27 ms 19576 KB Output is correct
5 Correct 19 ms 19676 KB Output is correct
6 Correct 27 ms 19576 KB Output is correct
7 Correct 29 ms 19804 KB Output is correct
8 Correct 29 ms 20216 KB Output is correct
9 Correct 29 ms 19832 KB Output is correct
10 Correct 24 ms 19704 KB Output is correct
11 Correct 29 ms 19704 KB Output is correct
12 Correct 27 ms 19704 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 67188 KB Output is correct
2 Correct 683 ms 40632 KB Output is correct
3 Correct 500 ms 53144 KB Output is correct
4 Correct 408 ms 38624 KB Output is correct
5 Correct 468 ms 39352 KB Output is correct
6 Correct 543 ms 40164 KB Output is correct
7 Correct 619 ms 40460 KB Output is correct
8 Correct 691 ms 40448 KB Output is correct
9 Correct 490 ms 69240 KB Output is correct
10 Correct 641 ms 47564 KB Output is correct
11 Correct 652 ms 42248 KB Output is correct
12 Correct 652 ms 40976 KB Output is correct
13 Correct 673 ms 40704 KB Output is correct
14 Correct 504 ms 68340 KB Output is correct
15 Correct 610 ms 42220 KB Output is correct
16 Correct 660 ms 40676 KB Output is correct
17 Correct 373 ms 34604 KB Output is correct
18 Correct 567 ms 40672 KB Output is correct
19 Correct 534 ms 40704 KB Output is correct
20 Correct 551 ms 40692 KB Output is correct