oj.uz

Submission #703280

# Submission time Handle Problem Language Result Execution time Memory
703280 2023-02-26T21:22:08 Z LucaGreg Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 1075 ms 148464 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[200010], maxVal[200010], maxSide[200010];
int queries[200010];
int resp[200010];
vector<int> cardsQueries[200010]; 
map<int, int> cc;
int segEntre[2000010], segMaior[2000010];

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;
    vector<int> aux;
    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:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 5 ms 5460 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5432 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 5 ms 5460 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5432 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 34 ms 9024 KB Output is correct
15 Correct 74 ms 12976 KB Output is correct
16 Correct 118 ms 17804 KB Output is correct
17 Correct 194 ms 20780 KB Output is correct
18 Correct 222 ms 20768 KB Output is correct
19 Correct 193 ms 20720 KB Output is correct
20 Correct 177 ms 20824 KB Output is correct
21 Correct 190 ms 21004 KB Output is correct
22 Correct 114 ms 17736 KB Output is correct
23 Correct 100 ms 14460 KB Output is correct
24 Correct 93 ms 13572 KB Output is correct
25 Correct 150 ms 18888 KB Output is correct
26 Correct 123 ms 17324 KB Output is correct
27 Correct 124 ms 18300 KB Output is correct
28 Correct 112 ms 18272 KB Output is correct
29 Correct 153 ms 19528 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 4 ms 5304 KB Output is correct
3 Correct 5 ms 5460 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5432 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 34 ms 9024 KB Output is correct
15 Correct 74 ms 12976 KB Output is correct
16 Correct 118 ms 17804 KB Output is correct
17 Correct 194 ms 20780 KB Output is correct
18 Correct 222 ms 20768 KB Output is correct
19 Correct 193 ms 20720 KB Output is correct
20 Correct 177 ms 20824 KB Output is correct
21 Correct 190 ms 21004 KB Output is correct
22 Correct 114 ms 17736 KB Output is correct
23 Correct 100 ms 14460 KB Output is correct
24 Correct 93 ms 13572 KB Output is correct
25 Correct 150 ms 18888 KB Output is correct
26 Correct 123 ms 17324 KB Output is correct
27 Correct 124 ms 18300 KB Output is correct
28 Correct 112 ms 18272 KB Output is correct
29 Correct 153 ms 19528 KB Output is correct
30 Correct 543 ms 32848 KB Output is correct
31 Correct 803 ms 49168 KB Output is correct
32 Correct 1075 ms 59336 KB Output is correct
33 Runtime error 940 ms 148464 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -