oj.uz

Submission #156052

# Submission time Handle Problem Language Result Execution time Memory
156052 2019-10-03T03:16:26 Z manh9203 허수아비 (JOI14_scarecrows) C++17
0 / 100
 1068 ms 30416 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 2e5 + 5;
int n,st[4*N],lazy[4*N];
long long ans;
pair<int,int> point[N];
vector<int> dmx,dmy;
map<int,int> idx,idy;
stack<int> s;
void push_down(int id,int l,int r){
	if(lazy[id] != 0){
		st[id] += lazy[id];
		if(l<r){
			lazy[id<<1] += lazy[id];
			lazy[id<<1|1] += lazy[id];
		}
		lazy[id] = 0;
	}
}
void update(int id,int l,int r,int i,int j,int x){
	push_down(id,l,r);
	if(l>j || r<i || i>j){
		return;
	}
	if(l>=i && r<=j){
		st[id] += x;
		if(l<r){
			lazy[id<<1] += x;
			lazy[id<<1|1] += x;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(id<<1, l, mid, i, j, x);
	update(id<<1|1, mid+1, r, i, j, x);
}
int get(int id,int l,int r,int i){
	push_down(id,l,r);
	if(l>i || r<i){
		return -1e9;
	}
	if(l == r){
		return st[id];
	}
	int mid = (l + r) >> 1;
	return max(get(id<<1, l, mid, i), get(id<<1|1, mid+1, r, i));
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> point[i].fi >> point[i].se;
		if(idx[point[i].fi] == 0){
			dmx.push_back(point[i].fi);
			idx[point[i].fi] = 1;
		}
		if(idy[point[i].se] == 0){
			dmy.push_back(point[i].se);
			idy[point[i].se] = 1;
		}
	}
	sort(dmx.begin(), dmx.end());
	sort(dmy.begin(), dmy.end());
	for(int i=0;i<dmx.size();i++){
		idx[dmx[i]] = i+1;
	}
	for(int i=0;i<dmy.size();i++){
		idy[dmy[i]] = i+1;
	}
	for(int i=1;i<=n;i++){
		point[i].fi = idx[point[i].fi];
		point[i].se = idy[point[i].se];
		swap(point[i].fi, point[i].se);
	}
	sort(point+1,point+1+n);
	for(int i=1;i<=n;i++){
		ans += get(1, 1, n, point[i].se);
		while(s.size() > 0 && s.top() < point[i].se){
			update(1, 1, n, point[i].se+1, n, -1);
			s.pop();
		}
		update(1, 1, n, point[i].se+1, n, 1);
		s.push(point[i].se);
	}
	cout << ans;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmx.size();i++){
              ~^~~~~~~~~~~
scarecrows.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmy.size();i++){
              ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1272 KB Output is correct
2 Incorrect 14 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 29316 KB Output is correct
2 Incorrect 1068 ms 30416 KB Output isn't correct
3 Halted 0 ms 0 KB -