oj.uz

Submission #1060620

# Submission time Handle Problem Language Result Execution time Memory
1060620 2024-08-15T19:18:34 Z oscar1f Examination (JOI19_examination) C++17
0 / 100
 1183 ms 118192 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23644 KB Output is correct
2 Correct 5 ms 23640 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 5 ms 23660 KB Output is correct
5 Correct 5 ms 23644 KB Output is correct
6 Correct 7 ms 23644 KB Output is correct
7 Correct 28 ms 26788 KB Output is correct
8 Correct 27 ms 26584 KB Output is correct
9 Correct 29 ms 26580 KB Output is correct
10 Correct 15 ms 26328 KB Output is correct
11 Correct 21 ms 25568 KB Output is correct
12 Incorrect 9 ms 25056 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 117724 KB Output is correct
2 Correct 1162 ms 117508 KB Output is correct
3 Correct 1074 ms 118192 KB Output is correct
4 Correct 375 ms 114972 KB Output is correct
5 Correct 505 ms 82020 KB Output is correct
6 Incorrect 126 ms 76472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 117724 KB Output is correct
2 Correct 1162 ms 117508 KB Output is correct
3 Correct 1074 ms 118192 KB Output is correct
4 Correct 375 ms 114972 KB Output is correct
5 Correct 505 ms 82020 KB Output is correct
6 Incorrect 126 ms 76472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23644 KB Output is correct
2 Correct 5 ms 23640 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 5 ms 23660 KB Output is correct
5 Correct 5 ms 23644 KB Output is correct
6 Correct 7 ms 23644 KB Output is correct
7 Correct 28 ms 26788 KB Output is correct
8 Correct 27 ms 26584 KB Output is correct
9 Correct 29 ms 26580 KB Output is correct
10 Correct 15 ms 26328 KB Output is correct
11 Correct 21 ms 25568 KB Output is correct
12 Incorrect 9 ms 25056 KB Output isn't correct
13 Halted 0 ms 0 KB -