Submission #1079768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079768		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	281 ms	28456 KiB

examination

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name "F"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

struct Pt{
    ll a, b, c;
    ll tp;
    Pt(){};
    Pt(ll _1, ll _2, ll _3, ll _4){
        a = _1; b = _2; c = _3;
        tp = _4;
    }
};

ll n,q,ans[maxn];
vector<Pt> v,tmp;

bool cmp(Pt x, Pt y){
    if(x.a == y.a){
        return x.tp < y.tp;
        if(x.b == y.b) return x.c > y.c;
        return x.b > y.b;
    }
    return x.a > y.a;
}

ordered_set S;

void cdq(ll l, ll r){
    if(l >= r) return;
    // cout << l << ' ' << r << endl;
    ll mid = (l+r)/2;
    cdq(l, mid);
    cdq(mid+1, r);
    ll p1 = l, p2 = mid+1;
    tmp.clear(); S.clear();
    while(p1 <= mid && p2 <= r){
        if(v[p1].b >= v[p2].b){
            if(v[p1].tp == 0){
                S.insert({v[p1].c, p1});
            }
            tmp.push_back(v[p1]);
            p1++;
        }else{
            if(v[p2].tp > 0){
                ans[v[p2].tp] += S.size() - S.order_of_key(make_pair(v[p2].c-1, inf));
            }
            tmp.push_back(v[p2]);
            p2++;
        }
    }
    while(p1 <= mid){
        tmp.push_back(v[p1]);
        p1++;
    }
    while(p2 <= r){
        if(v[p2].tp > 0){
            ans[v[p2].tp] += S.size() - S.order_of_key({v[p2].c-1, inf});
        }
        tmp.push_back(v[p2]);
        p2++;
    }
    for(ll i=l;i<=r;i++){
        v[i] = tmp[i-l];
    }

}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> q;
    f1(i,n){
        ll s,t; cin >> s >> t;
        v.push_back(Pt(s,t,s+t,0));
    }
    f1(i,q){
        ll x, y, z; cin >> x >> y >> z;
        v.push_back(Pt(x, y, z, i));
    }
    sort(v.begin(), v.end(), cmp);
    cdq(0, v.size()-1);
    f1(i,q) cout << ans[i] << '\n';
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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