oj.uz

Submission #202034

# Submission time Handle Problem Language Result Execution time Memory
202034 2020-02-13T07:06:12 Z dennisstar 허수아비 (JOI14_scarecrows) C++17
100 / 100
 1430 ms 12416 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N; pii P[200010]; ll A, S[200010];
void upd(int t, ll v) { while (t<=N) S[t]+=v, t+=t&-t; }
ll get(int t) { ll r=0; while (t) r+=S[t], t-=t&-t; return r; }

void f(int s, int e) {
	if (s==e) return ;
	int md=(s+e)/2;
	f(s, md); f(md+1, e);
	set<int> S; vector<pair<pii, int> > V;
	S.insert(N+1);
	for (int i=md, j; i>=s; i--) {
		j=*S.lower_bound(P[i].se); S.insert(P[i].se);
		V.eb(pii(P[i].se, 1), j-1);
	}S.clear();
	S.insert(0);
	for (int i=md+1, j; i<=e; i++) {
		j=*prev(S.lower_bound(P[i].se)); S.insert(P[i].se);
		V.eb(pii(j+1, 0), P[i].se);
	}
	sort(V.begin(), V.end());
	for (auto &i:V) {
		if (i.fi.se==0) upd(i.se, 1);
		if (i.fi.se==1) A+=get(i.se)-get(i.fi.fi-1);
	}
	for (auto &i:V) if (i.fi.se==0) upd(i.se, -1);
}

int main() {
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%d %d", &P[i].fi, &P[i].se);
	sort(P+1, P+1+N, [](pii &p1, pii &p2){ return p1.se<p2.se; });
	for (int i=1; i<=N; i++) P[i].se=i;
	sort(P+1, P+1+N);
	f(1, N);
	printf("%lld\n", A);
	return 0;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:38:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%d %d", &P[i].fi, &P[i].se);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 352 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 628 KB Output is correct
2 Correct 25 ms 632 KB Output is correct
3 Correct 23 ms 632 KB Output is correct
4 Correct 19 ms 628 KB Output is correct
5 Correct 24 ms 632 KB Output is correct
6 Correct 26 ms 632 KB Output is correct
7 Correct 24 ms 632 KB Output is correct
8 Correct 19 ms 628 KB Output is correct
9 Correct 23 ms 632 KB Output is correct
10 Correct 25 ms 632 KB Output is correct
11 Correct 26 ms 632 KB Output is correct
12 Correct 18 ms 632 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 11356 KB Output is correct
2 Correct 1430 ms 12124 KB Output is correct
3 Correct 1059 ms 12036 KB Output is correct
4 Correct 867 ms 12200 KB Output is correct
5 Correct 1078 ms 12364 KB Output is correct
6 Correct 1240 ms 12168 KB Output is correct
7 Correct 1354 ms 12276 KB Output is correct
8 Correct 1427 ms 12388 KB Output is correct
9 Correct 835 ms 11352 KB Output is correct
10 Correct 1110 ms 12104 KB Output is correct
11 Correct 1262 ms 12416 KB Output is correct
12 Correct 1360 ms 12364 KB Output is correct
13 Correct 1420 ms 12288 KB Output is correct
14 Correct 841 ms 11240 KB Output is correct
15 Correct 1274 ms 12240 KB Output is correct
16 Correct 1430 ms 12168 KB Output is correct
17 Correct 781 ms 7096 KB Output is correct
18 Correct 1370 ms 12324 KB Output is correct
19 Correct 1357 ms 12268 KB Output is correct
20 Correct 1339 ms 12312 KB Output is correct