Submission #1310604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310604		KhoaDuy	Examination (JOI19_examination)	C++17	100 / 100	352 ms	10180 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
struct cube{
    int a,b,c,idx;
};
const int MAXN=2*1e5;
vector<cube> v(MAXN);
int ans[MAXN];
bool cmp(cube &a,cube &b){
    if(a.a!=b.a){
        return (a.a<b.a);
    }
    return (a.idx>b.idx);
}
bool cmp2(cube &a,cube &b){
    return (a.b>b.b);
}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define orderset tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
void dnc(int l,int r){
    if(l==r){
        return;
    }
    orderset se;
    int mid=((l+r)>>1);
    dnc(l,mid),dnc(mid+1,r);
    sort(v.begin()+l,v.begin()+mid+1,cmp2);
    sort(v.begin()+mid+1,v.begin()+r+1,cmp2);;
    int ptr=mid;
    for(int i=l;i<=mid;i++){
        while(ptr+1<=r&&v[ptr+1].b>=v[i].b){
            ptr++;
            if(v[ptr].idx==-1){             
                se.insert({v[ptr].c,ptr});
            }
        }
        if(v[i].idx!=-1){
            ans[v[i].idx]+=(se.size()-se.order_of_key({v[i].c,0}));
        }
    }
}
signed main(){
    if(fopen("input.txt","r")){
        freopen("input.txt","r",stdin);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    for(int i=0;i<n;i++){
        int s,t;
        cin >> s >> t;
        v[i]={s,t,s+t,-1};
    }
    for(int i=0;i<q;i++){
        int x,y,z;
        cin >> x >> y >> z;
        v[i+n]={x,y,z,i};
    }
    sort(v.begin(),v.begin()+n+q,cmp);
    dnc(0,n+q-1);
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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