oj.uz

Submission #105705

# Submission time Handle Problem Language Result Execution time Memory
105705 2019-04-14T04:16:30 Z Pro_ktmr 허수아비 (JOI14_scarecrows) C++14
100 / 100
 2554 ms 50752 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

#define int long long

//RSQ セグメント木
struct SegmentTree{
private:
	int n;
	vector<int> nodes;
	const int DEFAULT = 0;
public:
	void init(int N){ //初期化する O(N)
		nodes.clear();
		n = 1;
		while(n < N) n *= 2;
		n = 2 * n -1;
		for(int i=0; i<n; i++) nodes.push_back(DEFAULT);
	}
	void update(int i, int x){ //値を変更する O(log N)
		i += n / 2;
		nodes[i] = x;
		while(i > 0){
			i = (i-1)/2; //親の取得は(i-1)/2
			nodes[i] = nodes[i*2+1] + nodes[i*2+2]; //子の取得はi*2+1,i*2+2
		}
	}
	int sum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
		if(r == -1) r = n/2+1;
		if(r <= a || b <= l) return DEFAULT; //交差する場合
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		int valueL = sum(a, b, k*2+1, l, (l+r)/2);
		int valueR = sum(a, b, k*2+2, (l+r)/2, r);
		return valueL + valueR;
	}
};

int N;
pair<int,int> point[200000];
//数学と同じ座標の取り方→xとyの大小関係一致
vector<int> zaatuX,zaatuY;

LL ans = 0;
void DevideConquer(int l, int r){
	if(r-l == 1) return;
	int m = (l+r)/2;

	vector<int> zaatu;
	for(int i=l; i<r; i++) zaatu.PB(point[i].second);
	sort(zaatu.begin(), zaatu.end());

	set<int> st1,st2;
	vector<pair<pair<int,int>,int>> kukan;
	for(int i=m-1; i>=l; i--){
		int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
		auto itr = st1.lower_bound(y);
		if(itr == st1.end()) kukan.PB(MP(MP(y,N),0));
		else kukan.PB(MP(MP(y,*itr),0));
		st1.insert(y);
	}
	for(int i=m; i<r; i++){
		int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
		auto itr = st2.lower_bound(y);
		if(itr == st2.begin()) kukan.PB(MP(MP(0,y),1));
		else{
			itr--;
			kukan.PB(MP(MP(*itr,y),1));
		}
		st2.insert(y);
	}


	sort(kukan.begin(), kukan.end());
	SegmentTree rsq; //右サイドの上端
	rsq.init(r-l);
	for(int i=0; i<kukan.size(); i++){
		if(kukan[i].second == 0){
			ans += rsq.sum(kukan[i].first.first, kukan[i].first.second);
		}
		else{
			rsq.update(kukan[i].first.second, 1);
		}
	}

	DevideConquer(l, m);
	DevideConquer(m, r);
}

signed main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", &point[i].first, &point[i].second);
		zaatuX.PB(point[i].first);
		zaatuY.PB(point[i].second);
	}
	sort(zaatuX.begin(), zaatuX.end());
	sort(zaatuY.begin(), zaatuY.end());
	for(int i=0; i<N; i++){
		point[i].first = lower_bound(zaatuX.begin(), zaatuX.end(), point[i].first) - zaatuX.begin();
		point[i].second = lower_bound(zaatuY.begin(), zaatuY.end(), point[i].second) - zaatuY.begin();
	}
	sort(point, point+N);

	//

	DevideConquer(0, N);
	printf("%lld\n", ans);

	return 0;
}

Compilation message

scarecrows.cpp: In function 'void DevideConquer(long long int, long long int)':
scarecrows.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<kukan.size(); i++){
               ~^~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:95:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d", &N);
              ~~^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d", &point[i].first, &point[i].second);
                 ~~~~~~~~~~~~~~~                  ^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
scarecrows.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &point[i].first, &point[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1668 KB Output is correct
2 Correct 37 ms 1684 KB Output is correct
3 Correct 31 ms 1724 KB Output is correct
4 Correct 28 ms 1744 KB Output is correct
5 Correct 33 ms 1772 KB Output is correct
6 Correct 34 ms 1688 KB Output is correct
7 Correct 35 ms 1796 KB Output is correct
8 Correct 31 ms 1716 KB Output is correct
9 Correct 34 ms 1696 KB Output is correct
10 Correct 36 ms 1772 KB Output is correct
11 Correct 36 ms 1772 KB Output is correct
12 Correct 25 ms 1600 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 49460 KB Output is correct
2 Correct 2405 ms 50708 KB Output is correct
3 Correct 1711 ms 50716 KB Output is correct
4 Correct 1543 ms 50688 KB Output is correct
5 Correct 1801 ms 50752 KB Output is correct
6 Correct 2157 ms 50572 KB Output is correct
7 Correct 2316 ms 50604 KB Output is correct
8 Correct 2435 ms 50600 KB Output is correct
9 Correct 1474 ms 50588 KB Output is correct
10 Correct 1870 ms 50636 KB Output is correct
11 Correct 2041 ms 50580 KB Output is correct
12 Correct 2554 ms 50500 KB Output is correct
13 Correct 2407 ms 50632 KB Output is correct
14 Correct 1327 ms 50648 KB Output is correct
15 Correct 2056 ms 50652 KB Output is correct
16 Correct 2389 ms 50596 KB Output is correct
17 Correct 1207 ms 31840 KB Output is correct
18 Correct 2266 ms 50624 KB Output is correct
19 Correct 2334 ms 50628 KB Output is correct
20 Correct 2074 ms 50660 KB Output is correct