Submission #1060620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060620		oscar1f	Examination (JOI19_examination)	C++17	0 / 100	1183 ms	118192 KiB

examination

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=100*1000+5,DECA=(1<<18);
int nbPers,nbReq,idRes1;
vector<tuple<int,int,int,int>> ordreParc;
set<int> listeRes1;
unordered_map<int,int> corres1;
vector<pair<int,int>> listeEvent[2*DECA];
int interCouv[2*DECA][2];
int arbreSom[2*DECA];
int rep[TAILLE_MAX];

void ajout(int pos,int val) {
    pos+=DECA;
    while (pos>0) {
        listeEvent[pos].push_back({val,-1});
        pos/=2;
    }
}

void quest(int pos,int posQuest,int valQuest,int idQuest) {
    if (interCouv[pos][0]>=idRes1 or interCouv[pos][1]<posQuest) {
        return;
    }
    else if (interCouv[pos][0]>=posQuest and interCouv[pos][1]<idRes1) {
        listeEvent[pos].push_back({valQuest,idQuest});
        //cout<<pos<<" ";
    }
    else {
        quest(2*pos,posQuest,valQuest,idQuest);
        quest(2*pos+1,posQuest,valQuest,idQuest);
    }
}

void ajoutSom(int pos) {
    while (pos>0) {
        arbreSom[pos]++;
        pos/=2;
    }
}

int calcSom(int deb,int fin) {
    if (deb==fin) {
        return arbreSom[deb];
    }
    if (deb%2==1) {
        return arbreSom[deb]+calcSom(deb+1,fin);
    }
    if (fin%2==0) {
        return arbreSom[fin]+calcSom(deb,fin-1);
    }
    return calcSom(deb/2,fin/2);
}

void calc(int pos) {
    if (listeEvent[pos].empty()) {
        return;
    }
    set<int> listeRes2;
    unordered_map<int,int> corres2;
    int idRes2=0,decal=1;
    //cout<<pos<<endl;
    for (auto i:listeEvent[pos]) {
        //cout<<i.first<<" "<<i.second<<endl;
        listeRes2.insert(i.first);
    }
    for (int i:listeRes2) {
        corres2[i]=idRes2;
        idRes2++;
    }
    while (decal<idRes2) {
        decal*=2;
    }
    for (int i=1;i<2*decal;i++) {
        arbreSom[i]=0;
    }
    for (auto i:listeEvent[pos]) {
        if (i.second==-1) {
            ajoutSom(corres2[i.first]+decal);
        }
        else {
            //cout<<"!"<<i.first<<" "<<i.second<<" : "<<calcSom(decal+corres2[i.first],decal+idRes2-1)<<endl;
            rep[i.second]+=calcSom(decal+corres2[i.first],decal+idRes2-1);
        }
    }
    //cout<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for (int i=0;i<DECA;i++) {
        interCouv[DECA+i][0]=i;
        interCouv[DECA+i][1]=i;
    }
    for (int i=DECA-1;i>0;i--) {
        interCouv[i][0]=interCouv[2*i][0];
        interCouv[i][1]=interCouv[2*i+1][1];
    }
    cin>>nbPers>>nbReq;
    int res1,res2,resTot,typeReq;
    for (int i=0;i<nbPers;i++) {
        cin>>res1>>res2;
        ordreParc.push_back(make_tuple(res1+res2,-1,res1,res2));
        listeRes1.insert(res1);
    }    
    for (int i=0;i<nbReq;i++) {
        cin>>res1>>res2>>resTot;
        ordreParc.push_back(make_tuple(resTot,i,res1,res2));
        listeRes1.insert(res1);
    }
    sort(ordreParc.begin(),ordreParc.end());
    reverse(ordreParc.begin(),ordreParc.end());
    for (int i:listeRes1) {
        corres1[i]=idRes1;
        //cout<<i<<" "<<idRes1<<endl;
        idRes1++;
    }
    /*for (int i=1;i<2*DECA;i++) {
        cout<<i<<" : "<<interCouv[i][0]<<" "<<interCouv[i][1]<<endl;
    }*/
    for (auto i:ordreParc) {
        resTot=get<0>(i);
        typeReq=get<1>(i);
        res1=get<2>(i);
        res2=get<3>(i);
        //cout<<resTot<<" "<<typeReq<<" "<<res1<<" "<<res2<<" : ";
        if (typeReq==-1) {
            ajout(corres1[res1],res2);
        }
        else {
            //cout<<"?"<<corres1[res1]<<" ";
            quest(1,corres1[res1],res2,typeReq);
        }
        //cout<<endl;
    }
    for (int i=0;i<2*DECA;i++) {
        calc(i);
    }
    for (int i=0;i<nbReq;i++) {
        cout<<rep[i]<<"\n";
    }
    return 0;
}
 

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