Submission #1227662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227662		luka_zecevic	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1409 ms	49728 KiB

fortune_telling2

#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff first
#define ss second
using namespace std;

const int N = 1e6 + 10;
int st[4 * N];
mt19937 rng(4051945);
bool tst = false;
int cnt = 0;
map < int , int > mapa;

void update(int index, int l, int r, int val, int pos)
{
    if(l > r || l > pos || r < pos) return;
    if(l == r) { st[index] = val; return; }
    int mid = (l + r) / 2;
    update(index * 2, l, mid, val, pos); update(index * 2 + 1, mid + 1, r, val, pos);
    st[index] = max(st[index * 2], st[index * 2 + 1]);
}

int get(int index, int l, int r, int L, int R)
{
    if(l > r || l > R || r < L) return 0;
    if(l >= L && r <= R) return st[index];
    int mid = (l + r) / 2;
    return max(get(index * 2, l, mid, L, R), get(index * 2 + 1, mid + 1, r, L, R));
}

void upd(int index, int l, int r, int val, int pos)
{
    if(l > r || l > pos || r < pos) return;
    if(l == r) { st[index] += val; return; }
    int mid = (l + r) / 2;
    upd(index * 2, l, mid, val, pos); upd(index * 2 + 1, mid + 1, r, val, pos);
    st[index] = st[index * 2] + st[index * 2 + 1];
}

int gt(int index, int l, int r, int L, int R)
{
    if(l > r || l > R || r < L) return 0;
    if(l >= L && r <= R) return st[index];
    int mid = (l + r) / 2;
    return gt(index * 2, l, mid, L, R) + gt(index * 2 + 1, mid + 1, r, L, R);
}

bool comp(pair < pair < int , int > , int > a, pair < pair < int , int > , int > b)
{
    return a.ss > b.ss;
}

int Rng(int l, int r)
{
    return l + rng() % (r - l + 1);
}

long long solve(int& n, int& k, vector < pair < pair < int , int > , int > >& vp, vector < int >& t)
{
    long long ans = 0;
    for(int i = 0; i < n; i++)
    {
        int curr = vp[i].ff.ff;
        for(int j = 0; j < k; j++)
        {
            if(t[j] >= curr)
            {
                if(curr == vp[i].ff.ff) curr = vp[i].ff.ss;
                else curr = vp[i].ff.ff;
            }
        }
        ans += curr;
    }
    return ans;
}

long long solveT(int& n, int& k, vector < pair < pair < int , int > , int > >& vp, vector < int >& t)
{
    if(tst) cout << "before everything: " << gt(1, 1, N - 10, 1, N - 10) << "\n";

    vector < int > aaa;
    for(int i = 0; i < n; i++) { aaa.push_back(vp[i].ff.ff); aaa.push_back(vp[i].ff.ss); }
    for(int i = 0; i < k; i++) aaa.push_back(t[i]);
    sort(begin(aaa), end(aaa));

    for(int i = 0; i < n * 2 + k; i++) if(mapa[aaa[i]] == 0) mapa[aaa[i]] = ++cnt;

    // for(int i = 0; i < n + k; i++) cout << aaa[i] << " ---> " << mapa[aaa[i]] << "\n";

    for(int i = 0; i < k; i++) update(1, 1, N - 10, i + 1, mapa[t[i]]);

    for(int i = 0; i < n; i++) vp[i].ss = get(1, 1, N - 10, mapa[min(vp[i].ff.ff, vp[i].ff.ss)] , mapa[max(vp[i].ff.ff, vp[i].ff.ss)] - 1) - 1;
    if(tst)
    {
        cout << "\n";
        for(auto it : vp) cout << it.ss << " ";
        cout << "!\n";
    }
    sort(begin(vp), end(vp), comp);

    for(int i = 0; i < k; i++) update(1, 1, N - 10, 0, mapa[t[i]]);

    int j = k - 1;
    long long ans = 0;
    if(tst) cout << "before loop: " << gt(1, 1, N - 10, 1, N - 10) << "\n";

    for(int i = 0; i < n; i++)
    {
        while(j > vp[i].ss)
        {
          upd(1, 1, N - 10, 1, mapa[t[j]]); j--; 
          if(tst) cout << "updating: " << j + 1 << " " << gt(1, 1, N - 10, 1, N - 10) << "\n";
        }

        int trn = gt(1, 1, N - 10, mapa[max(vp[i].ff.ff, vp[i].ff.ss)], N - 10);
        // cout << " { { " << vp[i].ff.ff << " , " << vp[i].ff.ss << " } , " << vp[i].ss << " } -> ";
        // cout << "number of flips: " << trn << "\n";
        bool a = false;
        if(vp[i].ff.ff > vp[i].ff.ss)
        {
            if(trn % 2) a = !a;
        }
        else
        {
            a = (j != -1); // true -> b, false -> a
            if(trn % 2) a = !a;
        }
        if(tst) cout << "dodajem: " << (a ? vp[i].ff.ss : vp[i].ff.ff) << ", broj operacija: " << trn << "\n";
        ans += (a ? vp[i].ff.ss : vp[i].ff.ff);
    }

    for(int i = 0; i < 4 * N; i++) st[i] = 0;

    return ans;
}

int main()
{
    FAST;
    int n, k; cin >> n >> k;
    vector < pair < pair < int , int > , int > > vp(n);
    vector < int > t(k);
    for(int i = 0; i < n; i++) cin >> vp[i].ff.ff >> vp[i].ff.ss;
    for(int i = 0; i < k; i++) cin >> t[i];
    cout << solveT(n, k, vp, t) << "\n";

    // for(int i = 0; i < 1000; i++)
    // {
    //     int n = Rng(1, 5);
    //     int k = Rng(1, 5);
    //     vector < pair < pair < int , int > , int > > vp(n);
    //     vector < int > t(k);

    //     for(int i = 0; i < n; i++) vp[i] = make_pair(make_pair(Rng(1, 1000000000), Rng(1, 1000000000)) , 0);
    //     for(int i = 0; i < k; i++) t[i] = Rng(1, 1000000000);
    //     // cout << i << "\n";
    //     if(solve(n, k, vp, t) != solveT(n, k, vp, t))
    //     {
    //         cout << "Pao!\n";
    //         tst = true;
    //         cout << solve(n, k, vp, t) << "    " << solveT(n, k, vp, t) << "!!!!\n";
    //         cout << n << " " << k << "\n";
    //         for(auto it : vp) cout << it.ff.ff << " " << it.ff.ss << "\n";
    //         for(auto it : t) cout << it << "\n";
    //         break;
    //     }
    // }
    return 0;
}

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