oj.uz

Submission #49625

# Submission time Handle Problem Language Result Execution time Memory
49625 2018-06-01T06:23:10 Z mra2322001 Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 1744 ms 30588 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(mid==0) break;
                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(mid==0) break;
                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(max(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 2 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 85 ms 2276 KB Output is correct
2 Correct 198 ms 4056 KB Output is correct
3 Correct 344 ms 6000 KB Output is correct
4 Correct 438 ms 7760 KB Output is correct
5 Correct 421 ms 7892 KB Output is correct
6 Correct 89 ms 7892 KB Output is correct
7 Correct 1744 ms 7996 KB Output is correct
8 Correct 70 ms 7996 KB Output is correct
9 Correct 61 ms 7996 KB Output is correct
10 Correct 105 ms 7996 KB Output is correct
11 Correct 303 ms 7996 KB Output is correct
12 Correct 58 ms 7996 KB Output is correct
13 Incorrect 1049 ms 7996 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

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