Submission #703281

#	Time	Username	Problem	Language	Result	Execution time	Memory
703281		LucaGreg	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1631 ms	101524 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define int long long int

const int INF = 2000000000000000000;
int minVal[400010], maxVal[400010], maxSide[400010];
int queries[400010];
int resp[400010];
vector<int> cardsQueries[400010]; 
map<int, int> cc;
int segEntre[4000010], segMaior[4000010];
vector<int> aux;

void updateSegEntre(int pseg, int ini, int fim, int p, int val){
    if(p<ini || p>fim) return;
    if(ini==fim){
        segEntre[pseg] = val;
        return;
    }
    int m = (ini + fim)/2;
    int l = 2*pseg;
    int r = 2*pseg + 1;
    updateSegEntre(l, ini, m, p, val);
    updateSegEntre(r, m + 1, fim, p, val);
    segEntre[pseg] = max(segEntre[l], segEntre[r]);
}

int querySegEntre(int pseg, int ini, int fim, int qini, int qfim){
    if(qini>fim || qfim<ini) return 0;
    if(qini<=ini && fim<=qfim) return segEntre[pseg];
    int m = (ini + fim)/2;
    int l = 2*pseg;
    int r = 2*pseg + 1;
    return max(querySegEntre(l, ini, m, qini, qfim), querySegEntre(r, m + 1, fim, qini, qfim));
}

void updateSegMaior(int pseg, int ini, int fim, int p){
    if(p<ini || p>fim) return;
    if(ini==fim){
        segMaior[pseg]++;
        return;
    }
    int m = (ini + fim)/2;
    int l = 2*pseg;
    int r = 2*pseg + 1;
    updateSegMaior(l, ini, m, p);
    updateSegMaior(r, m + 1, fim, p);
    segMaior[pseg] = segMaior[l] + segMaior[r];
}

int querySegMaior(int pseg, int ini, int fim, int qini, int qfim){
    if(qini>fim || qfim<ini) return 0;
    if(qini<=ini && fim<=qfim) return segMaior[pseg];
    int m = (ini + fim)/2;
    int l = 2*pseg;
    int r = 2*pseg + 1;
    return querySegMaior(l, ini, m, qini, qfim) + querySegMaior(r, m + 1, fim, qini, qfim);
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0);
    int n, q; cin>>n>>q;
    for(int i=1;i<=n;i++){
        int ai, bi; cin>>ai>>bi;
        minVal[i] = min(ai, bi);
        maxVal[i] = max(ai, bi);
        if(ai<bi) maxSide[i] = 1;
        aux.pb(ai);
        aux.pb(bi);
    }
    for(int i=1;i<=q;i++){
        int ti; cin>>ti;
        queries[i] = ti;
        aux.pb(ti);
    }
    sort(aux.begin(), aux.end());
    int newVal = 1;
    for(int i=0;i<(int)aux.size();i++){
        if(cc[aux[i]]==0){
            cc[aux[i]] = newVal;
            newVal++;
        }
    }
    int maxSeg = newVal - 1;
    //cout<<maxSeg<<"\n";
    for(int i=1;i<=q;i++) updateSegEntre(1, 1, maxSeg, cc[queries[i]], i);
    for(int i=1;i<=n;i++){
        int p = querySegEntre(1, 1, maxSeg, cc[minVal[i]], cc[maxVal[i]] - 1);
        //cout<<i<<" "<<p<<"\n";
        if(p==0 && maxSide[i]==1) resp[i]++;
        cardsQueries[p].pb(i);
    }
    for(int i=q;i>=0;i--){
        for(int j=0;j<(int)cardsQueries[i].size();j++){
            int qtdMaior = querySegMaior(1, 1, maxSeg, cc[maxVal[cardsQueries[i][j]]], maxSeg);
            resp[cardsQueries[i][j]] += qtdMaior;
            //cout<<i<<" "<<cardsQueries[i][j]<<" "<<qtdMaior<<"\n";
        }
        if(i>0) updateSegMaior(1, 1, maxSeg, cc[queries[i]]);
    }
    int soma = 0;
    for(int i=1;i<=n;i++){
        //cout<<i<<" "<<resp[i]<<"\n";
        if((resp[i]%2)==0) soma += maxVal[i];
        else soma += minVal[i];
    }
    cout<<soma<<"\n";

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65