oj.uz

Submission #259050

# Submission time Handle Problem Language Result Execution time Memory
259050 2020-08-07T05:12:29 Z Namnamseo 허수아비 (JOI14_scarecrows) C++17
100 / 100
 452 ms 10988 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())

using namespace std;
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

int y[200010];
pp dt[200010];
int n;

const int M=262144;

int tree[M*2];

void upd(int pos,int val){
	pos+=M;
	while(pos){
		tree[pos] += val;
		pos >>= 1;
	}
}

int rangeSum(int a,int b){
	int ret=0;
	a+=M; b+=M;
	while(a<=b){
		if(a%2==1) ret+=tree[a++];
		if(b%2==0) ret+=tree[b--];
		a/=2; b/=2;
	}
	return ret;
}

ll work(vector<int>& v){
	if(sz(v) <= 1) return 0;
	int n=sz(v);
	int minv = *min_element(all(v));
	int maxv = *max_element(all(v));
	int mid=(minv+maxv)/2;

	ll ans=0;
	vector<int> v1, v2;
	stack<int> s, ss;

	for(int i=0; i<n; ++i){
		if(v[i] <= mid){
			v1.pb(v[i]);
			while(sz(s) && v[s.top()] < v[i]){
				upd(s.top(), -1);
				s.pop();
			}
			s.push(i);
			upd(i, 1);
		} else {
			v2.pb(v[i]);
			while(sz(ss) && v[ss.top()] > v[i]){
				ss.pop();
			}
			ans += rangeSum((sz(ss))?(ss.top()+1):0, i-1);
			ss.push(i);
		}
	}
	while(s.size()){
		upd(s.top(), -1); s.pop();
	}
	ans += work(v1) + work(v2);
	return ans;
}

int main(){
	read(n);
	vector<int> ys;
	for(int i=1; i<=n; ++i){
		read(dt[i].first, dt[i].second);
		ys.push_back(dt[i].second);
	}
	sort(dt+1, dt+n+1);
	sort(all(ys));
	vector<int> v;
	for(int i=1; i<=n; ++i){
		v.pb(lower_bound(all(ys), dt[i].second)-ys.begin());
	}
	printf("%lld\n", work(v));
	return 0;
}

Compilation message

scarecrows.cpp: In function 'void read(int&)':
scarecrows.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 628 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 8 ms 640 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 8 ms 640 KB Output is correct
9 Correct 9 ms 640 KB Output is correct
10 Correct 10 ms 712 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 8760 KB Output is correct
2 Correct 420 ms 10728 KB Output is correct
3 Correct 393 ms 10984 KB Output is correct
4 Correct 354 ms 10696 KB Output is correct
5 Correct 358 ms 10860 KB Output is correct
6 Correct 371 ms 10856 KB Output is correct
7 Correct 393 ms 10988 KB Output is correct
8 Correct 414 ms 10856 KB Output is correct
9 Correct 373 ms 10728 KB Output is correct
10 Correct 391 ms 10988 KB Output is correct
11 Correct 403 ms 10860 KB Output is correct
12 Correct 413 ms 10816 KB Output is correct
13 Correct 431 ms 10964 KB Output is correct
14 Correct 389 ms 10808 KB Output is correct
15 Correct 410 ms 10724 KB Output is correct
16 Correct 452 ms 10876 KB Output is correct
17 Correct 266 ms 7108 KB Output is correct
18 Correct 432 ms 10732 KB Output is correct
19 Correct 412 ms 10604 KB Output is correct
20 Correct 394 ms 10600 KB Output is correct