Submission #1066626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066626		Boycl07	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	301 ms	135608 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define int ll
#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "FFILL"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }


const int N = 2e5 + 3;
const int LIM = (1 << 16) + 3;
const int INF = 1e9 + 1;
const int LOG = 19;

int n, k, m;

struct fenwick_tree
{
    int bit[3 * N];

    void update(int u, int v)
    {
        for(; u; u -= u & -u) bit[u] ^= v;
    }

    int get(int u)
    {
        int res = 0;
        for(; u <= m; u += u & -u) res ^= bit[u];
        return res;
    }
} BIT;


int a[N], b[N], p[N];

int col[N];

int st[3 * N][LOG + 1];
int lg[3 * N];

vector<int> zip;

void compress()
{
    rep(i, n) zip.pb(a[i]), zip.pb(b[i]);
    rep(i, k) zip.pb(p[i]);
    sort(all(zip));
    zip.resize(unique(all(zip)) - zip.begin());
    m = sz(zip);

    rep(i, n)
    {
        a[i] = upper_bound(all(zip), a[i]) - zip.begin();
        b[i] = upper_bound(all(zip), b[i]) - zip.begin();
    }
    rep(i, k) p[i] = upper_bound(all(zip), p[i]) - zip.begin();
}

int get(int l, int r)
{
    if(l > r) return 0;
    int len = lg[r - l + 1];

    return max(st[l][len], st[r - (1 << len) + 1][len]);
}

int last_assign[N];

void find_last_assign()
{
    rep(i, k)
        maximize(st[p[i]][0], i);
    lg[1] = 0;
    forn(i, 2, m) lg[i] = lg[i >> 1] + 1;
    for(int j = 1; (1 << j) <= m; ++j)
        for(int i = 1; i + (1 << j) - 1 <= m; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

    rep(i, n) if(last_assign[i] = get(a[i], b[i] - 1))
        col[i] = 1;
}

vector<pii> queries[N];

void count_flip()
{
    rep(i, n) queries[last_assign[i] + 1].pb({i, b[i]});
    ford(i, k, 1)
    {
        BIT.update(p[i], 1);
        for(auto &[idx, u] : queries[i])
            col[idx] ^= BIT.get(u);
    }
}

void solve()
{
    cin >> n >> k;
    rep(i, n)
    {
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) col[i] = 1, swap(a[i], b[i]);
        else col[i] = 0;
    }
    rep(i, k) cin >> p[i];

    compress();
    find_last_assign();
    count_flip();
    ll res = 0;
    rep(i, n) res += zip[(col[i] ? b[i] : a[i]) - 1];
    cout << res;


}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen("note.inp", "r"))
    {
        freopen("note.inp", "r", stdin);
        freopen("note.out", "w", stdout);
    }


    while(TC--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void find_last_assign()':
fortune_telling2.cpp:96:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   96 |             st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
      |                                                       ~~^~~
fortune_telling2.cpp:98:33: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   98 |     rep(i, n) if(last_assign[i] = get(a[i], b[i] - 1))
      |                  ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen("note.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen("note.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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