Submission #162020

#	Time	Username	Problem	Language	Result	Execution time	Memory
162020		Alexa2001	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	478 ms	15912 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;
typedef long long ll;


int n, m, P;
int A[Nmax], B[Nmax], Op[Nmax];

vector<int> all;
vector<pair<int,int>> ask[Nmax];


#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


class SegTree
{
    int mx[Nmax<<2], cnt[Nmax<<2];


    void update(int node, int st, int dr, int pos, int val = 0)
    {
        if(!val) ++cnt[node];

        if(st == dr)
        {
            if(val)
                mx[node] = max(mx[node], val);
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos, val);
            else update(right_son, mid+1, dr, pos, val);

        if(val) mx[node] = max(mx[left_son], mx[right_son]);
    }

    int query_max(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R) return mx[node];

        int res = 0;
        if(L <= mid) res = max(res, query_max(left_son, st, mid, L, R));
        if(mid < R) res = max(res, query_max(right_son, mid+1, dr, L, R));
        return res;
    }

    int query_cnt(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R) return cnt[node];

        int res = 0;
        if(L <= mid) res += query_cnt(left_son, st, mid, L, R);
        if(mid < R) res += query_cnt(right_son, mid+1, dr, L, R);
        return res;
    }
public:
    void update(int x, int val = 0)
    {
        x = lower_bound( all.begin(), all.end(), x ) - all.begin();
        update(1, 0, P-1, x, val);
    }

    int query_max(int x, int y)
    {
        x = lower_bound( all.begin(), all.end(), x ) - all.begin();
        y = upper_bound( all.begin(), all.end(), y ) - all.begin() - 1;

        if(x > y) return 0;
        return query_max(1, 0, P-1, x, y);
    }

    int query_cnt(int x)
    {
        x = upper_bound( all.begin(), all.end(), x ) - all.begin() - 1;
        if(x < 0) return 0;
        return query_cnt(1, 0, P-1, 0, x);
    }
} aint;

void solve(int pos)
{
    int mn, mx;
    mn = min(A[pos], B[pos]);
    mx = max(A[pos], B[pos]);

    int last = aint.query_max( mn, mx-1 );
    ask[last].push_back( { pos, mn } );
}

void prepare()
{
    int i;
    for(i=1; i<=m; ++i) all.push_back(Op[i]);
    sort(all.begin(), all.end());
    all.erase( unique(all.begin(), all.end()), all.end() );

    P = all.size();

    for(i=1; i<=m; ++i) aint.update( Op[i], i );
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    int i;
    for(i=1; i<=n; ++i) cin >> A[i] >> B[i];
    for(i=1; i<=m; ++i) cin >> Op[i];

    prepare();

    ll ans = 0;
    for(i=1; i<=n; ++i) solve(i);

    for(i=m; i>=0; --i)
    {
        for(auto it : ask[i])
        {
            int cnt;
            cnt = m - i - aint.query_cnt(it.second - 1);

            int curr;

            if(i)
            {
                if(cnt % 2 == 1) curr = min(A[it.first], B[it.first]);
                    else curr = max(A[it.first], B[it.first]);
            }
            else
            {
                if(cnt % 2 == 0) curr = A[it.first];
                    else curr = B[it.first];
            }

            ans += curr;
        }

        if(!i) break;
        aint.update( Op[i] );
    }

    cout << ans << '\n';

    return 0;
}

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