oj.uz

Submission #1060650

# Submission time Handle Problem Language Result Execution time Memory
1060650 2024-08-15T20:23:48 Z oscar1f Examination (JOI19_examination) C++17
2 / 100
 3000 ms 30648 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],vraiRep[TAILLE_MAX];
vector<pair<int,int>> listeInit;

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);
        listeInit.push_back({res1,res2});
    }    
    for (int i=0;i<nbReq;i++) {
        cin>>res1>>res2>>resTot;
        for (auto j:listeInit) {
            if (j.first>=res1 and j.second>=res2 and j.first+j.second>=resTot) {
                vraiRep[i]++;
            }
        }
        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<<vraiRep[i]<<"\n";
        /*if (rep[i]!=vraiRep[i]) {
            cout<<-1<<endl;
            return 0;
        }*/
    }
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24412 KB Output is correct
2 Correct 5 ms 24436 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 5 ms 24412 KB Output is correct
7 Correct 62 ms 27424 KB Output is correct
8 Correct 61 ms 27448 KB Output is correct
9 Correct 67 ms 27240 KB Output is correct
10 Correct 51 ms 27096 KB Output is correct
11 Correct 54 ms 26200 KB Output is correct
12 Correct 44 ms 25936 KB Output is correct
13 Correct 57 ms 27596 KB Output is correct
14 Correct 57 ms 27388 KB Output is correct
15 Correct 57 ms 27548 KB Output is correct
16 Correct 31 ms 26192 KB Output is correct
17 Correct 38 ms 27084 KB Output is correct
18 Correct 14 ms 25944 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 30648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 30648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24412 KB Output is correct
2 Correct 5 ms 24436 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 5 ms 24412 KB Output is correct
7 Correct 62 ms 27424 KB Output is correct
8 Correct 61 ms 27448 KB Output is correct
9 Correct 67 ms 27240 KB Output is correct
10 Correct 51 ms 27096 KB Output is correct
11 Correct 54 ms 26200 KB Output is correct
12 Correct 44 ms 25936 KB Output is correct
13 Correct 57 ms 27596 KB Output is correct
14 Correct 57 ms 27388 KB Output is correct
15 Correct 57 ms 27548 KB Output is correct
16 Correct 31 ms 26192 KB Output is correct
17 Correct 38 ms 27084 KB Output is correct
18 Correct 14 ms 25944 KB Output is correct
19 Execution timed out 3066 ms 30648 KB Time limit exceeded
20 Halted 0 ms 0 KB -