Submission #49617

#	Time	Username	Problem	Language	Result	Execution time	Memory
49617		mra2322001	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	2045 ms	6244 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;
struct data{
    int x, id;
    bool operator <(data g){
        return x < g.x;
    }
} a[N], b[N];

int n, k, t[N], answer[N];

void up(int node, int l, int r, int i, int val){
    if(r < i || l > i) return ;
    if(l==r){
        t[node] = val;
        return ;
    }
    int m = (l + r)/2;
    up(node*2, l, m, i, val);
    up(node*2+1, m + 1, r, i, val);
    t[node] = max(t[2*node], t[2*node+1]);
}

int get2(int node, int l, int r, int i, int j){
    if(r < i || l > j) return 0;
    if(l >= i && r <= j) return t[node];
    int m = (l + r)/2;
    return max(get2(node*2, l, m, i, j), get2(node*2+1, m + 1, r, i, j));
}

void update(int x, int val){
    up(1, 1, k, x, val);
}

int get1(int x, int y){
    return get2(1, 1, k, x, y);
}

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].x >> b[i].x;
        b[i].id = a[i].id = i;
    }

    f1(i, k){
        int u; cin >> u;
        update(i, u);
    }
    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].x) 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].x) 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 += ll(b[i].x);
        else res += ll(a[i].x);
    }
    cout << res;
}

Compilation message (stderr)

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

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