Submission #1015570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015570		andrei_iorgulescu	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	3071 ms	8992 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

int n,k,a[200005],b[200005],t[200005];
int g;
bool tr[1005][1005];
vector<int> lol;
int pa[200005],pb[200005];
pair<int,int> vv[400005];
bool sp[200005];
int f1[400005],f2[400005];

void solve(vector<int> op)
{
    set<int> ss;
    for (auto it : op)
        ss.insert(it);
    vector<int> vls;
    for (auto it : ss)
        vls.push_back(it);
    vls.push_back((int)2e9);
    int i0 = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        while (vls[i0] < f1[i])
            i0++;
        if (f2[i] < 0)
            pb[-f2[i]] = i0;
        else
            pa[f2[i]] = i0;
    }
    for (int i = 0; i < vls.size(); i++)
    {
        for (int j = 0; j < vls.size(); j++)
        {
            int x0 = vls[i];
            int x = vls[i],y = vls[j];
            int cnt_swap = 0;
            for (auto it : op)
            {
                if (it >= x)
                    swap(x,y),cnt_swap ^= 1;
            }
            if (cnt_swap)
                tr[i][j] = true;
            else
                tr[i][j] = false;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if ((!sp[i] and tr[pa[i]][pb[i]]) or (sp[i] and tr[pb[i]][pa[i]]))
            swap(a[i],b[i]),sp[i] ^= 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= k; i++)
        cin >> t[i];
    for (int i = 1; i <= n; i++)
    {
        vv[2 * i - 1] = {a[i],i};
        vv[2 * i] = {b[i],-i};
    }
    sort(vv + 1,vv + 2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        f1[i] = vv[i].first;
        f2[i] = vv[i].second;
    }
    g = 50;
    for (int i = 1; i <= k; i += g)
    {
        vector<int> op;
        for (int j = i; j <= k and j < i + g; j++)
            op.push_back(t[j]);
        solve(op);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i];
    cout << ans;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void solve(std::vector<int>)':
fortune_telling2.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < vls.size(); i++)
      |                     ~~^~~~~~~~~~~~
fortune_telling2.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 0; j < vls.size(); j++)
      |                         ~~^~~~~~~~~~~~
fortune_telling2.cpp:37:17: warning: unused variable 'x0' [-Wunused-variable]
   37 |             int x0 = vls[i];
      |                 ^~

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