oj.uz

Submission #703281

# Submission time Handle Problem Language Result Execution time Memory
703281 2023-02-26T21:24:14 Z LucaGreg Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1631 ms 101524 KB 
#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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9956 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10172 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 8 ms 10068 KB Output is correct
8 Correct 8 ms 10068 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 9 ms 10068 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9956 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10172 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 8 ms 10068 KB Output is correct
8 Correct 8 ms 10068 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 9 ms 10068 KB Output is correct
14 Correct 43 ms 13396 KB Output is correct
15 Correct 71 ms 17100 KB Output is correct
16 Correct 130 ms 21700 KB Output is correct
17 Correct 187 ms 24244 KB Output is correct
18 Correct 220 ms 24344 KB Output is correct
19 Correct 190 ms 24276 KB Output is correct
20 Correct 192 ms 24368 KB Output is correct
21 Correct 210 ms 24568 KB Output is correct
22 Correct 124 ms 21832 KB Output is correct
23 Correct 103 ms 18500 KB Output is correct
24 Correct 99 ms 17596 KB Output is correct
25 Correct 123 ms 22808 KB Output is correct
26 Correct 115 ms 21024 KB Output is correct
27 Correct 131 ms 21812 KB Output is correct
28 Correct 120 ms 21796 KB Output is correct
29 Correct 167 ms 23032 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9956 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10172 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 8 ms 10068 KB Output is correct
8 Correct 8 ms 10068 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 9 ms 10068 KB Output is correct
14 Correct 43 ms 13396 KB Output is correct
15 Correct 71 ms 17100 KB Output is correct
16 Correct 130 ms 21700 KB Output is correct
17 Correct 187 ms 24244 KB Output is correct
18 Correct 220 ms 24344 KB Output is correct
19 Correct 190 ms 24276 KB Output is correct
20 Correct 192 ms 24368 KB Output is correct
21 Correct 210 ms 24568 KB Output is correct
22 Correct 124 ms 21832 KB Output is correct
23 Correct 103 ms 18500 KB Output is correct
24 Correct 99 ms 17596 KB Output is correct
25 Correct 123 ms 22808 KB Output is correct
26 Correct 115 ms 21024 KB Output is correct
27 Correct 131 ms 21812 KB Output is correct
28 Correct 120 ms 21796 KB Output is correct
29 Correct 167 ms 23032 KB Output is correct
30 Correct 564 ms 35420 KB Output is correct
31 Correct 835 ms 51096 KB Output is correct
32 Correct 1096 ms 60172 KB Output is correct
33 Correct 1608 ms 95112 KB Output is correct
34 Correct 481 ms 35604 KB Output is correct
35 Correct 1631 ms 100936 KB Output is correct
36 Correct 1629 ms 100692 KB Output is correct
37 Correct 1532 ms 100536 KB Output is correct
38 Correct 1547 ms 100936 KB Output is correct
39 Correct 1520 ms 100756 KB Output is correct
40 Correct 1533 ms 101524 KB Output is correct
41 Correct 1552 ms 100668 KB Output is correct
42 Correct 1482 ms 100460 KB Output is correct
43 Correct 973 ms 83092 KB Output is correct
44 Correct 853 ms 84104 KB Output is correct
45 Correct 884 ms 87436 KB Output is correct
46 Correct 878 ms 63756 KB Output is correct
47 Correct 731 ms 48828 KB Output is correct
48 Correct 1042 ms 71716 KB Output is correct
49 Correct 1029 ms 72252 KB Output is correct