Submission #1205170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205170		justinlgl20	Examination (JOI19_examination)	C++20	100 / 100	298 ms	22680 KiB

examination

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ost;

int32_t main() {
	cin.tie(0)->sync_with_stdio(false);
	int n,q;cin>>n>>q;vector<pair<pii,pii>>e(n+q);for(int i=0;i<n;i++){cin>>e[i].f.f>>e[i].f.s;e[i].s={-1ll,-1ll};}
	for(int i=n;i<n+q;i++){cin>>e[i].f.f>>e[i].f.s>>e[i].s.f;e[i].s.s=i-n;}
	vector<int> ans(q,0);
	sort(all(e),[&](auto a,auto b){
		int va=a.f.f+a.f.s;if(a.s.f!=-1)va=a.s.f;
		int vb=b.f.f+b.f.s;if(b.s.f!=-1)vb=b.s.f;
		if(va!=vb)return va>vb;// bigger sum first
		if(a.s.f==-1 and b.s.f!=-1)return true;
		if(a.s.f!=-1 and b.s.f==-1)return false;
		return false;
	});
	for(auto i:e){
		dbg(i.f.f,i.f.s,i.s.f,i.s.s);
		int v=i.f.f+i.f.s;if(i.s.f!=-1)v=i.s.f;
		dbg(v);
	}
	function<void(int,int)> cdq=[&](int l,int r){
		int tm=(l+r)>>1;
		if(l==r)return;
		// get students in l and answer stuff on right
		vector<pii> kids;
		for(int i=l;i<=tm;i++){
			if(e[i].s.f==-1)kids.emplace_back(e[i].f);
		}
		vector<pair<pii,int>> queries;
		for(int i=tm+1;i<=r;i++){
			if(e[i].s.f!=-1)queries.emplace_back(e[i].f,e[i].s.s);
		}
		sort(all(kids));reverse(all(kids));sort(all(queries));reverse(all(queries));
		int inx=0;
		ost s;int cnt=0;
		for(auto i:queries){
			while(inx<kids.size() and kids[inx].f>=i.f.f){
				s.insert(make_pair(kids[inx].s,cnt++));
				inx++;
			}
			ans[i.s]+=s.size()-s.order_of_key(make_pair(i.f.s,-1ll));
		}
		cdq(l,tm);
		cdq(tm+1,r);
	};
	cdq(0,e.size()-1);
	for(int i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57