Submission #997998

#	Time	Username	Problem	Language	Result	Execution time	Memory
997998		anHiep	Examination (JOI19_examination)	C++14	100 / 100	1055 ms	77980 KiB

examination

//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~     //
//         Nhan qua khong no chung ta thu gi          //
//                 Vay nen dung oan han               //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~     //
//                                                    //    
//                       _oo0oo_                      //
//                      o8888888o                     //
//                      88" . "88                     //					  
//                      (| -_- |)                     //
//                      0\  =  /0                     //
//                    ___/`---'\___                   //
//                  .' \\|     |// '.                 //
//                 / \\|||  :  |||// \                //  			  
//                / _||||| -:- |||||- \               // 			  
//               |   | \\\  -  /// |   |              //			  
//               | \_|  ''\---/''  |_/ |              //			  
//               \  .-\__  '-'  ___/-. /              //			  
//             ___'. .'  /--.--\  `. .'___            //			  
//          ."" '<  `.___\_<|>_/___.' >' "".          //  		  
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |        //		  
//         \  \ `_.   \_ __\ /__ _/   .-` /  /        //    	  
//     =====`-.____`.___ \_____/___.-`___.-'=====     //     
//                       `=---='                      //
//                                                    //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~     //
//   Duc Phat noi day phu ho Code con chay khong Bug  //
//                 Nam mo a di da phat                //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~     //

#include<bits/stdc++.h>
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "Orz_chUoNgnn"
#endif

using namespace std;

#define fi first 
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 1e6;
int tc, tt = 1;

struct student {
	ll a, b, c;
	ll in, q;
} a[N + 5];
#define vi vector<student> 
int n, q;
vector<int> f;
map<int, int> pos;
ll ans[N + 5];
struct fenwick_tree {
	ll ft[N + 5];
	void update(int pos, int val) {
		int idx = pos;
		while(idx <= N) {
			ft[idx] += val;
			idx += (idx & (-idx));
		}
	}
	ll get(int pos) {
		int idx = pos;
		ll ans = 0;
		while(idx > 0) {
			ans += ft[idx];
			idx -= (idx & (-idx));
		}
		return ans;
	}
} ft;
vi cdq(int l, int r) {
	vi f;
	vector<int> record;
	if(l == r) {
		f.pb(a[l]);
		return f;
	}
	int mid = (l + r)/2;
	vi a = cdq(l, mid);
	vi b = cdq(mid + 1, r);
	int i = 0, j = 0, cnt = 0;
	while(i < (int)a.size() && j < (int)b.size()) {
		if(a[i].b > b[j].b) {
			f.pb(a[i]);
			if(a[i].in) {
				cnt++;
				ft.update(pos[a[i].c], 1);
				record.pb(pos[a[i].c]);
			}
			i++;
		}
		else {
			if(!b[j].in) 
				ans[b[j].q] += cnt - ft.get(pos[b[j].c]);
			f.pb(b[j]);
			j++;
		}
	}
	while(i < (int)a.size()) {f.pb(a[i]); i++;}
	while(j < (int)b.size()) {
		if(!b[j].in)
			ans[b[j].q] += cnt - ft.get(pos[b[j].c]);
		f.pb(b[j]); 
		j++;
	}
	for(auto x: record) ft.update(x, -1);
	return f;
}
void solve() {
	cin>>n>>q;
	for(int i=1; i<=n + q; i++) {
		a[i].a = a[i].b = a[i].c = a[i].in = 0;
	}
	for(int i=1; i<=n; i++) {
		cin>>a[i].a>>a[i].b;
		a[i].c = a[i].a + a[i].b;
		a[i].in = 1;
	}
	for(int i=n + 1; i<=n + q; i++) {
		cin>>a[i].a>>a[i].b>>a[i].c;
		a[i].a--;
		a[i].b--;
		a[i].c--;
		a[i].q = i - n;
	}
	n += q;
	for(int i=1; i<=n; i++) {
		f.pb(a[i].a);
		f.pb(a[i].b);
		f.pb(a[i].c);
	}
	sort(f.begin(), f.end());
	f.erase(unique(f.begin(), f.end()), f.end());
	for(int i=0; i<(int)f.size(); i++) pos[f[i]] = i + 1;
	sort(a + 1, a + 1 + n, [](student x, student y){
		if(x.a != y.a) return x.a > y.a;
		if(x.b != y.b) return x.b < y.b;
		return x.c < y.c;
	}); 
	cdq(1, n);
	for(int i=1; i<=q; i++)
		cout<<ans[i]<<'\n';
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
    for(int tc=1; tc<=tt; tc++) solve();
    cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

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