Submission #1314101

#TimeUsernameProblemLanguageResultExecution timeMemory
1314101Robert_juniorExamination (JOI19_examination)C++20
100 / 100
287 ms15896 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define ins insert
const int N = 6e5 + 100, M = 3e3 + 7;
const int mod  = 1e9 + 7, inf = 1e9;
int f[N], res[N], n;
struct str{
    int x, y, z, i;
};
void add(int idx, int val){
    for(; idx < N; idx |= (idx + 1)){
        f[idx] += val;
    }
}
int get(int r){
    int res = 0;
    for(; r >= 0; r = (r & (r + 1)) - 1){
        res += f[r];
    }
    return res;
}
vector<str>v;
void cdq(int l, int r){
    if(l + 1 == r) return;
    int m = (l + r) / 2;
    cdq(l, m), cdq(m, r);
    vector<int>rec;
    vector<str>tmp;
    int a = l, b = m, sum = 0;
    while(a < m && b < r){
        if(v[a].y > v[b].y){
            if(v[a].i == 0){
                add(v[a].z, 1);
                sum++;
                rec.pb(v[a].z);
            }
            tmp.pb(v[a++]);
        }
        else res[v[b].i] += sum - get(v[b].z), tmp.pb(v[b++]);
    }
    while(a < m) tmp.pb(v[a++]);
    while(b < r) res[v[b].i] += sum - get(v[b].z), tmp.pb(v[b++]);
    for(int i = l; i < r; i++) v[i] = tmp[i - l];
    for(auto it : rec) add(it, -1);
}
void solve(){
    int n, q;
    cin>>n>>q;
    vector<int>v1;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin>>x>>y;
        v.pb({x, y, x + y, 0});
        v1.pb(x), v1.pb(y), v1.pb(x + y);
    }
    for(int i = 1; i <= q; i++){
        int a, b, c;
        cin>>a>>b>>c;
        v1.pb(a - 1);
        v1.pb(b - 1);
        v1.pb(c - 1);
        v.pb({a - 1, b - 1, c - 1, i});
    }
    sort(all(v1));
    for(int i = 0; i  < n + q; i++){
        v[i].x = upper_bound(all(v1), v[i].x) - v1.begin();
        v[i].y = upper_bound(all(v1), v[i].y) - v1.begin();
        v[i].z = upper_bound(all(v1), v[i].z) - v1.begin();
    }
    sort(v.begin(), v.end(), [&](auto a, auto b) { 
        return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x); 
    }); 
    cdq(0, n + q);
    for(int i = 1; i <= q; i++){
        cout<<res[i]<<' ';
    }
}
main(){
    	//freopen(".in", "r", stdin);
    	//freopen(".out", "w", stdout);
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

examination.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...