Submission #105713

#	Time	Username	Problem	Language	Result	Execution time	Memory
105713		Pro_ktmr	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	1232 ms	31664 KiB

matryoshka

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP(a,b) make_pair(a,b)

//RSQ セグメント木
struct SegmentTree{
private:
	int n;
	vector<long long> nodes;
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(0);
	}
	void add(int i, long long 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
		}
	}
	long long 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 0; //交差する場合
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		long long valueL = sum(a, b, k*2+1, l, (l+r)/2);
		long long valueR = sum(a, b, k*2+2, (l+r)/2, r);
		return valueL + valueR;
	}
};

int N,Q;
vector<pair<int,int> > v,q;
vector<int> zaatuB;
vector<pair<pair<int,int>, int> > all;
multiset<pair<int,int> > s;
SegmentTree st;
int ans[200000];

int main(){
	cin >> N >> Q;
	for(int i=0; i<N; i++){
		int A,B;
		cin >> A >> B;
		v.push_back(MP(A,B));
		zaatuB.push_back(B);
	}
	for(int i=0; i<Q; i++){
		int a,b;
		cin >> a >> b;
		q.push_back(MP(a,b));
		zaatuB.push_back(b);
	}
	sort(zaatuB.begin(), zaatuB.end());
	for(int i=0; i<N; i++){
		all.push_back(MP(MP(v[i].first, lower_bound(zaatuB.begin(), zaatuB.end(), v[i].second)-zaatuB.begin()), Q));
		swap(all.back().first.second, all.back().second);
	}
	for(int i=0; i<Q; i++){
		all.push_back(MP(MP(q[i].first, lower_bound(zaatuB.begin(), zaatuB.end(), q[i].second)-zaatuB.begin()), i));
		swap(all.back().first.second, all.back().second);
	}
	sort(all.begin(), all.end());
	reverse(all.begin(), all.end());
	for(int i=0; i<all.size(); i++){
		swap(all[i].first.second, all[i].second);
	}

	st.init(zaatuB.size());
	multiset<pair<int,int> > s2;
	for(int i=0; i<all.size(); i++){
		if(i != 0 && all[i-1].first.first != all[i].first.first){
			for(auto itr=s2.begin(); itr!=s2.end(); itr++) s.insert(*itr);
			s2.clear();
		}
		//cout << all[i].first.first << " " << all[i].first.second << " " << all[i].second << endl;
		if(all[i].second == Q){
			auto itr = s.lower_bound(MP(all[i].first.second+1,-1));
			while(s.size() != 0 && itr != s.end()){
				if(itr->first > all[i].first.second/* && itr->second > all[i].first.first*/){
					st.add(itr->first, -1);
					s.erase(itr);
					break;
				}
				itr++;
			}
			s2.insert(MP(all[i].first.second, all[i].first.first));
			st.add(all[i].first.second, 1);
		}
		else{
			ans[all[i].second] = st.sum(0, all[i].first.second+1);
		}
	}
	for(int i=0; i<Q; i++) cout << ans[i] << endl;

	return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++){
               ~^~~~~~~~~~~
matryoshka.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++){
               ~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49