Submission #1079861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079861		KhoaDuy	Examination (JOI19_examination)	C++14	100 / 100	579 ms	37380 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
struct cube{
    int a,b,c,idx;
};
const int MAXN=1e5;
int ans[MAXN]={0};
int bit[2*MAXN+1]={0};
void update(int i,int x){
    for(;i<=2*MAXN;i+=(i&(-i))){
        bit[i]+=x;
    }
}
int pre(int i){
    int curr=0;
    for(;i;i-=(i&(-i))){
        curr+=bit[i];
    }
    return curr;
}
int query(int l,int r){
    return pre(r)-pre(l-1);
}
bool cmp(cube &a,cube &b){
    return (a.b>b.b);
}
bool cmp2(cube &a,cube &b){
    if(a.a!=b.a){
        return (a.a<b.a);
    }
    if(a.b!=b.b){
        return (a.b<b.b);
    }
    if(a.c!=b.c){
        return (a.c<b.c);
    }
    if(a.idx!=b.idx){
        return (a.idx>b.idx);
    }
}
void dnc(vector<cube> &v){
    if(v.size()<=1){
        return;
    }
    int mid=(v.size()>>1);
    vector<cube> v1,v2;
    for(int i=0;i<mid;i++){
        v1.push_back(v[i]);
    }
    for(int i=mid;i<v.size();i++){
        v2.push_back(v[i]);
    }
    dnc(v1),dnc(v2);
    sort(v.begin(),v.end(),cmp);
    /*cout << "GOT" << endl;
    cout << "V1: " << endl;
    for(int i=0;i<v1.size();i++){
        cout << v1[i].a << ' ' << v1[i].b << ' ' << v1[i].c << ' ' << v1[i].idx << endl;
    }
    cout << "V2: " << endl;
    for(int i=0;i<v2.size();i++){
        cout << v2[i].a << ' ' << v2[i].b << ' ' << v2[i].c << ' ' << v2[i].idx << endl;
    }*/
    int ptr=0;
    for(int i=0;i<v2.size();i++){
        while(ptr<v1.size()&&v1[ptr].b>v2[i].b){
            if(v1[ptr].idx!=-1){
                ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN);
            }
            ptr++;
        }
        if(v2[i].idx==-1){
            update(v2[i].c,1);
        }
    }
    while(ptr<v1.size()){
        if(v1[ptr].idx!=-1){
            ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN);
        }
        ptr++;
    }
    for(int i=0;i<v2.size();i++){
        if(v2[i].idx==-1){
            update(v2[i].c,-1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    vector<cube> v;
    map<int,int> mp;
    for(int i=0;i<n;i++){
        int s,t;
        cin >> s >> t;
        v.push_back({s,t,s+t,-1});
        mp[s+t]=1;
    }
    for(int i=0;i<q;i++){
        int x,y,z;
        cin >> x >> y >> z;
        v.push_back({x,y,z,i});
        mp[z]=1;
    }
    int idx=1;
    for(pair<const int,int> &x:mp){
        x.second=idx;
        idx++;
    }
    for(int i=0;i<v.size();i++){
        v[i].c=mp[v[i].c];
    }
    for(int i=0;i<v.size();i++){
    //    cout << v[i].a << ' ' << v[i].b << ' ' << v[i].c << ' ' << v[i].idx << endl;
    }
    sort(v.begin(),v.end(),cmp2);
    dnc(v);
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

examination.cpp: In function 'void dnc(std::vector<cube>&)':
examination.cpp:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=mid;i<v.size();i++){
      |                   ~^~~~~~~~~
examination.cpp:67:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp:68:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(ptr<v1.size()&&v1[ptr].b>v2[i].b){
      |               ~~~^~~~~~~~~~
examination.cpp:78:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     while(ptr<v1.size()){
      |           ~~~^~~~~~~~~~
examination.cpp:84:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:114:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:117:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp: In function 'bool cmp2(cube&, cube&)':
examination.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

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