oj.uz

Submission #930456

# Submission time Handle Problem Language Result Execution time Memory
930456 2024-02-19T20:29:02 Z parlimoos Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 59 ms 54192 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

int n , q;
vector<arr(2)> a;
vector<int> ops;
vector<int> seg[400001];
int seginf[400001][2];

void buildSeg(int l = 0 , int r = q - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r;
    if(l == r) seg[i].pb(ops[l]);
    else{
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
        seg[i].resize(r - l + 1);
        merge(seg[i << 1].bg() , seg[i << 1].end() , seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , seg[i].bg());
    }
}
int bsSeg(int i , int l , int r){
    if(i == 1){
        auto itr = lb(seg[i].bg() , seg[i].end() , l);
        if(itr == seg[i].end() or *itr > r) return seginf[i][0];
    }
    if(seginf[i][0] == seginf[i][1]) return seginf[i][1] + 1;
    auto itr = lb(seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , l);
    if(itr != seg[(i << 1) | 1].end() and *itr <= r) return bsSeg((i << 1) | 1 , l , r);
    return bsSeg(i << 1 , l , r);
}
int cntSeg(int l , int r , int i , int val){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return (seginf[i][1] - seginf[i][0] + 1 - int(lb(seg[i].bg() , seg[i].end() , val) - seg[i].bg()));
    if(seginf[i][1] >= l and seginf[i][0] <= r) return (cntSeg(l , r , i << 1 , val) + cntSeg(l , r , (i << 1) | 1 , val));
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 0 ; i < n ; i++){
        int d1 , d2;
        cin >> d1 >> d2;
        a.pb({d1 , d2});
    }
    for(int i = 0 ; i < q ; i++){
        int d;
        cin >> d;
        ops.pb(d);
    }
    ll o = 0;
    buildSeg();
    for(auto el : a){
        if(el[0] == el[1]){
            o += el[0];
        }else if(el[0] < el[1]){
            int inx = bsSeg(1 , el[0] , el[1] - 1);
            int d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]);
            if(inx == 0){
                if((d & 1)) o += el[1];
                else o += el[0];
            }else{
                if((d & 1)) o += el[0];
                else o += el[1];
            }
        }else if(el[1] < el[0]){
            int inx = bsSeg(1 , el[1] , el[0] - 1);
            int d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[0]);
            if((d & 1)) o += el[1];
            else o += el[0];
        }
    }
    cout << o;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 5 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 4 ms 10764 KB Output is correct
8 Correct 4 ms 10844 KB Output is correct
9 Correct 6 ms 10680 KB Output is correct
10 Correct 4 ms 10768 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10916 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 5 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 4 ms 10764 KB Output is correct
8 Correct 4 ms 10844 KB Output is correct
9 Correct 6 ms 10680 KB Output is correct
10 Correct 4 ms 10768 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10916 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct
14 Correct 14 ms 14304 KB Output is correct
15 Correct 26 ms 16088 KB Output is correct
16 Correct 40 ms 17812 KB Output is correct
17 Correct 55 ms 19080 KB Output is correct
18 Correct 52 ms 19160 KB Output is correct
19 Correct 56 ms 19160 KB Output is correct
20 Correct 58 ms 19148 KB Output is correct
21 Correct 43 ms 19180 KB Output is correct
22 Correct 30 ms 18684 KB Output is correct
23 Correct 31 ms 18644 KB Output is correct
24 Correct 33 ms 18648 KB Output is correct
25 Correct 31 ms 18864 KB Output is correct
26 Correct 33 ms 18896 KB Output is correct
27 Correct 56 ms 19152 KB Output is correct
28 Correct 34 ms 19156 KB Output is correct
29 Correct 47 ms 19160 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 5 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 4 ms 10764 KB Output is correct
8 Correct 4 ms 10844 KB Output is correct
9 Correct 6 ms 10680 KB Output is correct
10 Correct 4 ms 10768 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10916 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct
14 Correct 14 ms 14304 KB Output is correct
15 Correct 26 ms 16088 KB Output is correct
16 Correct 40 ms 17812 KB Output is correct
17 Correct 55 ms 19080 KB Output is correct
18 Correct 52 ms 19160 KB Output is correct
19 Correct 56 ms 19160 KB Output is correct
20 Correct 58 ms 19148 KB Output is correct
21 Correct 43 ms 19180 KB Output is correct
22 Correct 30 ms 18684 KB Output is correct
23 Correct 31 ms 18644 KB Output is correct
24 Correct 33 ms 18648 KB Output is correct
25 Correct 31 ms 18864 KB Output is correct
26 Correct 33 ms 18896 KB Output is correct
27 Correct 56 ms 19152 KB Output is correct
28 Correct 34 ms 19156 KB Output is correct
29 Correct 47 ms 19160 KB Output is correct
30 Runtime error 59 ms 54192 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -