Submission #49622

#	Time	Username	Problem	Language	Result	Execution time	Memory
49622		mra2322001	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	1843 ms	30464 KiB

fortune_telling2

#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(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;
                        }
                    }
                }
                else{
                    if(max(save[j].first, save[j].second)){
                        if(save[j].first){
                            if(y==2) 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 (stderr)

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65