oj.uz

Submission #448201

# Submission time Handle Problem Language Result Execution time Memory
448201 2021-07-29T09:30:28 Z blue Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1202 ms 79848 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxK = 200'000;
const int logN = 20;
const long long INF = 1'000'000'000'000'000'000LL;

int N, K;
vector<long long> T(1+maxK);

struct segtree
{
    int l;
    int r;
    vector<long long> v;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r)
        {
            v.push_back(T[l]);
        }
        else
        {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);

            for(int x: left->v) v.push_back(x);
            for(int y: right->v) v.push_back(y);
            sort(v.begin(), v.end());
        }
    }

    int query(int L, int R, long long X, long long Y)
    {
        // cerr << l << ' ' << r << " query " << L << ' ' << R << ' ' << X << ' ' << Y << '\n';
        // cerr << "v = ";
        // for(long long w1: v) cerr << w1 << ' ';
        // cerr << '\n';

        if(X > Y) return 0;

        L = max(L, l);
        R = min(R, r);
        if(L > R) return 0;

        if(R < l || r < L) return 0;
        else if(L <= l && r <= R)
        {
            // cerr << "check A\n";
            int lo = -1;
            for(int bit = logN; bit >= 0; bit--)
            {
                if(lo + (1 << bit) >= v.size()) continue;
                if(v[lo + (1 << bit)] >= X) continue;
                lo += (1 << bit);
            }
            // cerr << "check B\n";
            lo++;
            if(lo >= v.size() || v[lo] < X || Y < v[lo]) return 0;

            // cerr << "check C\n";

            int hi = -1;
            for(int bit = logN; bit >= 0; bit--)
            {
                if(hi + (1 << bit) >= v.size()) continue;
                if(v[hi + (1 << bit)] > Y) continue;
                hi += (1 << bit);
            }
            if(hi == -1 || hi >= v.size() || v[hi] < X || Y < v[hi] || hi < lo) return 0;

            // cerr << "check D\n";

            // cerr << l << ' ' << r << " query " << L << ' ' << R << ' ' << X << ' ' << Y << " done \n";

            return hi-lo+1;
        }
        else return left->query(L, R, X, Y) + right->query(L, R, X, Y);
    }

    int get_last(long long A, long long B)
    {
        // cerr << l << ' ' << r << " get last " << A << ' ' << B << '\n';
        if(l == r) return l;
        else if(right->query(1, K, A, B) >= 1)
            return right->get_last(A, B);
        else
            return left->get_last(A, B);

        // cerr << l << ' ' << r << " get last " << A << ' ' << B << " done\n";
    }
};

int main()
{
    cin >> N >> K;

    long long A[N+1], B[N+1];
    for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];

    for(int j = 1; j <= K; j++) cin >> T[j];
    T[0] = -1;

    segtree S(0, K);

    long long res = 0;

    // cerr << "check\n";

    for(int i = 1; i <= N; i++)
    {
        // cerr << "\n\n";
        // cerr << "i = " << i << '\n';
        if(A[i] == B[i])
        {
            res += A[i];
            continue;
        }

        int last_pos = S.get_last(min(A[i], B[i]),  max(A[i], B[i]) - 1);

        // cerr << "last_pos = " << last_pos << '\n';

        if(last_pos == 0)
        {
            // cerr << "case 1, no force up\n";
            int Q = S.query(1, K, max(A[i], B[i]), INF);

            // cerr << "Q = " << Q << '\n';

            if(Q % 2 == 0) res += A[i];
            else res += B[i];
            // cerr << i << ' ' << "B1 - done \n";
        }
        else
        {
            // cerr << "case 2, force up at " << last_pos << '\n';
            int Q = S.query(last_pos + 1, K, max(A[i], B[i]), INF);

            // cerr << "Q = " << Q << '\n';

            if(Q % 2 == 0) res += max(A[i], B[i]);
            else res += min(A[i], B[i]);

            // cerr << i << ' ' << "B2 - done \n";
        }
    }

    cout << res << '\n';
}

Compilation message

fortune_telling2.cpp: In member function 'int segtree::query(int, int, long long int, long long int)':
fortune_telling2.cpp:67:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 if(lo + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
fortune_telling2.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if(lo >= v.size() || v[lo] < X || Y < v[lo]) return 0;
      |                ~~~^~~~~~~~~~~
fortune_telling2.cpp:80:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 if(hi + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
fortune_telling2.cpp:84:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             if(hi == -1 || hi >= v.size() || v[hi] < X || Y < v[hi] || hi < lo) return 0;
      |                            ~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 3 ms 2124 KB Output is correct
3 Correct 4 ms 2124 KB Output is correct
4 Correct 4 ms 2128 KB Output is correct
5 Correct 5 ms 2124 KB Output is correct
6 Correct 4 ms 2124 KB Output is correct
7 Correct 5 ms 2124 KB Output is correct
8 Correct 4 ms 2124 KB Output is correct
9 Correct 4 ms 2124 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 4 ms 2124 KB Output is correct
12 Correct 4 ms 2304 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 3 ms 2124 KB Output is correct
3 Correct 4 ms 2124 KB Output is correct
4 Correct 4 ms 2128 KB Output is correct
5 Correct 5 ms 2124 KB Output is correct
6 Correct 4 ms 2124 KB Output is correct
7 Correct 5 ms 2124 KB Output is correct
8 Correct 4 ms 2124 KB Output is correct
9 Correct 4 ms 2124 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 4 ms 2124 KB Output is correct
12 Correct 4 ms 2304 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 41 ms 5648 KB Output is correct
15 Correct 83 ms 9548 KB Output is correct
16 Correct 128 ms 12152 KB Output is correct
17 Correct 190 ms 17600 KB Output is correct
18 Correct 180 ms 17608 KB Output is correct
19 Correct 195 ms 17588 KB Output is correct
20 Correct 187 ms 17584 KB Output is correct
21 Correct 174 ms 17600 KB Output is correct
22 Correct 150 ms 17184 KB Output is correct
23 Correct 179 ms 17088 KB Output is correct
24 Correct 156 ms 17304 KB Output is correct
25 Correct 145 ms 17184 KB Output is correct
26 Correct 160 ms 17316 KB Output is correct
27 Correct 200 ms 17600 KB Output is correct
28 Correct 181 ms 17568 KB Output is correct
29 Correct 217 ms 17576 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 3 ms 2124 KB Output is correct
3 Correct 4 ms 2124 KB Output is correct
4 Correct 4 ms 2128 KB Output is correct
5 Correct 5 ms 2124 KB Output is correct
6 Correct 4 ms 2124 KB Output is correct
7 Correct 5 ms 2124 KB Output is correct
8 Correct 4 ms 2124 KB Output is correct
9 Correct 4 ms 2124 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 4 ms 2124 KB Output is correct
12 Correct 4 ms 2304 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 41 ms 5648 KB Output is correct
15 Correct 83 ms 9548 KB Output is correct
16 Correct 128 ms 12152 KB Output is correct
17 Correct 190 ms 17600 KB Output is correct
18 Correct 180 ms 17608 KB Output is correct
19 Correct 195 ms 17588 KB Output is correct
20 Correct 187 ms 17584 KB Output is correct
21 Correct 174 ms 17600 KB Output is correct
22 Correct 150 ms 17184 KB Output is correct
23 Correct 179 ms 17088 KB Output is correct
24 Correct 156 ms 17304 KB Output is correct
25 Correct 145 ms 17184 KB Output is correct
26 Correct 160 ms 17316 KB Output is correct
27 Correct 200 ms 17600 KB Output is correct
28 Correct 181 ms 17568 KB Output is correct
29 Correct 217 ms 17576 KB Output is correct
30 Correct 384 ms 73112 KB Output is correct
31 Correct 580 ms 74424 KB Output is correct
32 Correct 763 ms 76292 KB Output is correct
33 Correct 1169 ms 79676 KB Output is correct
34 Correct 341 ms 72748 KB Output is correct
35 Correct 1192 ms 79728 KB Output is correct
36 Correct 1161 ms 79764 KB Output is correct
37 Correct 1202 ms 79708 KB Output is correct
38 Correct 1166 ms 79808 KB Output is correct
39 Correct 1184 ms 79832 KB Output is correct
40 Correct 1000 ms 79556 KB Output is correct
41 Correct 1142 ms 79848 KB Output is correct
42 Correct 1148 ms 79792 KB Output is correct
43 Correct 929 ms 79092 KB Output is correct
44 Correct 899 ms 79064 KB Output is correct
45 Correct 926 ms 79048 KB Output is correct
46 Correct 942 ms 77856 KB Output is correct
47 Correct 955 ms 77664 KB Output is correct
48 Correct 1117 ms 79796 KB Output is correct
49 Correct 1075 ms 79744 KB Output is correct