Submission #189439

#	Time	Username	Problem	Language	Result	Execution time	Memory
189439		dndhk	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	1353 ms	44896 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;

int N, Q, K;
struct S{
	int a, b, idx;
	bool operator <(const S &x)const{
		return a<x.a;
	}
};
vector<S> query;
vector<pii> vt;
int ans[MAX_N+1];
vector<int> v;
map<int, int> mp;

void input(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		int a, b; scanf("%d%d", &a, &b);
		v.pb(b);
		vt.pb({a, b});
	}
	for(int i=1; i<=Q; i++){
		int a, b; scanf("%d%d", &a, &b);
		v.pb(b);
		query.pb({a, b, i});
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	K = v.size();
	for(int i=0 ;i<v.size(); i++){
		mp[v[i]] = i+1;
	}
	for(int i=0; i<vt.size(); i++){
		vt[i].second = mp[vt[i].second];
	}
	for(int i=0; i<query.size(); i++){
		query[i].b = mp[query[i].b];
	}
	sort(query.begin(), query.end());
	sort(vt.begin(), vt.end());}
struct SEG{
	struct NODE{
		int l, r;
		int sum;
	};
	vector<NODE> seg;
	int SZ;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, int y){
		update(0, 1, SZ, x, y);
	}
	void update(int idx, int s, int e, int x, int y){
		seg[idx].sum+=y;
		if(s==e)	return;
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
	}
	int Sum(int x, int y){
		return sum(0, 1, SZ, x, y);
	}
	int sum(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y)	return seg[idx].sum;
		if(x>e || y<s)	return 0;
		return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
	}
}Seg;

multiset<int> st;
void upd(pii x){
	multiset<int>::iterator it = st.upper_bound(x.second);
	if(it!=st.end()){
		st.erase(it);
		int k = (*it);
		Seg.Update(k, -1);
	}
	Seg.Update(x.second, 1);
}

vector<int> prv;

int main(){
	input();
	Seg.Init(K);
	while(!query.empty()){
		int pa = -1;
		S q = query.back(); query.pop_back();
		while(!vt.empty() && vt.back().first>=q.a){
			if(pa!=-1){
				if(pa!=vt.back().first){
					while(!prv.empty()){
						st.insert(prv.back()); prv.pop_back();
					}
				}
			}
			pa = vt.back().first;
			upd(vt.back());
			prv.pb(vt.back().second);
			vt.pop_back();
		}
		while(!prv.empty()){
			st.insert(prv.back()); prv.pop_back();
		}
		ans[q.idx] = Seg.Sum(1, q.b);
	}
	for(int i=1; i<=Q; i++){
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

matryoshka.cpp: In function 'void input()':
matryoshka.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0 ;i<v.size(); i++){
               ~^~~~~~~~~
matryoshka.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
matryoshka.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
matryoshka.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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