oj.uz

Submission #49620

# Submission time Handle Problem Language Result Execution time Memory
49620 2018-06-01T06:00:06 Z mra2322001 Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 1978 ms 39172 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 200002;

ll a[N], b[N], c[N], t[N][18];
int n, k, answer[N];

void rmq(){
    f1(i, k) t[i][0] = c[i];
    int l = log2(k);
    f1(j, l){
        int u = (1 << j);
        for(int i = 1; i <= n - u + 1; i++){
            t[i][j] = max(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int get1(int u, int v){
    int x = log2(v - u + 1);
    int res = max(t[u][x], t[v - (1 << x) + 1][x]);
    return res;
}

int Ans(int x){if(x==1) return 2;return 1;}
main(){
    ios_base::sync_with_stdio(0);


    cin >> n >> k;
    f1(i, n){
        cin >> a[i] >> b[i];
    }

    f1(i, k){
        cin >> c[i];
    }
    rmq();
    vector <pair <int, int> > save;
    f1(i, n){
        /// assume a[i] could be ans[1]
        /// find 1 and 2
        while(save.size()) save.pop_back();
        int k1 = k, k2 = k;
        while(1){
            int p1, p2;
            int l = 1, r = k1, ans = 0;
            while(l <= r){
                int mid = (l + r)/2;
                if(get1(mid, k1) >= a[i]) ans = mid, l = mid + 1;
                else r = mid - 1;
            } p1 = ans;
            l = 1, r = k2, ans = 0;
            while(l <= r){
                int mid = (l + r)/2;
                if(get1(mid, k2) >= b[i]) ans = mid, l = mid + 1;
                else r = mid - 1;
            } p2 = ans;
            save.push_back(make_pair(p1, p2));
            if(p1 != p2) break;
            if(p1==0) break;
            k1 = p1 - 1, k2 = p2 - 1;
        }
        int y = 2; /// now i belong to Ans(2)
        if(save.size() == 1){
            if(save[0].first > save[0].second) answer[i] = Ans(1);
            else answer[i] = Ans(2);
        }
        else{
            for(int j = save.size() - 1; j >= 0; j--){
                if(min(save[j].first, save[j].second)){
                    if(save[j].first==save[j].second){
                        if(y==2) y = 1;
                        else y = 2;
                    }
                    else{
                        if(save[j].first > save[j].second){
                            y = 1;
                        }
                        else{
                            y = 2;
                        }
                    }
                }
            }
            answer[i] = Ans(y);
        }
    }
    ll res = 0;
    f1(i, n){
        if(answer[i]==2) res += b[i];
        else res += a[i];
    }
    cout << res;
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 2280 KB Output is correct
2 Correct 188 ms 3980 KB Output is correct
3 Correct 402 ms 5992 KB Output is correct
4 Correct 511 ms 7656 KB Output is correct
5 Correct 468 ms 9096 KB Output is correct
6 Correct 106 ms 9708 KB Output is correct
7 Correct 1978 ms 11592 KB Output is correct
8 Correct 77 ms 11968 KB Output is correct
9 Correct 59 ms 12808 KB Output is correct
10 Correct 103 ms 13564 KB Output is correct
11 Correct 312 ms 14356 KB Output is correct
12 Correct 61 ms 14884 KB Output is correct
13 Incorrect 1104 ms 16260 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 39172 KB Output isn't correct
2 Halted 0 ms 0 KB -