oj.uz

Submission #1066626

# Submission time Handle Problem Language Result Execution time Memory
1066626 2024-08-20T03:30:55 Z Boycl07 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 301 ms 135608 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15208 KB Output is correct
3 Correct 3 ms 15448 KB Output is correct
4 Correct 3 ms 15568 KB Output is correct
5 Correct 3 ms 15448 KB Output is correct
6 Correct 3 ms 15452 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15452 KB Output is correct
9 Correct 3 ms 15504 KB Output is correct
10 Correct 2 ms 15248 KB Output is correct
11 Correct 2 ms 15416 KB Output is correct
12 Correct 2 ms 15248 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15208 KB Output is correct
3 Correct 3 ms 15448 KB Output is correct
4 Correct 3 ms 15568 KB Output is correct
5 Correct 3 ms 15448 KB Output is correct
6 Correct 3 ms 15452 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15452 KB Output is correct
9 Correct 3 ms 15504 KB Output is correct
10 Correct 2 ms 15248 KB Output is correct
11 Correct 2 ms 15416 KB Output is correct
12 Correct 2 ms 15248 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 12 ms 22496 KB Output is correct
15 Correct 22 ms 27868 KB Output is correct
16 Correct 36 ms 33232 KB Output is correct
17 Correct 47 ms 38756 KB Output is correct
18 Correct 46 ms 38864 KB Output is correct
19 Correct 48 ms 38864 KB Output is correct
20 Correct 47 ms 38864 KB Output is correct
21 Correct 45 ms 39292 KB Output is correct
22 Correct 32 ms 31948 KB Output is correct
23 Correct 31 ms 29052 KB Output is correct
24 Correct 27 ms 26488 KB Output is correct
25 Correct 36 ms 33616 KB Output is correct
26 Correct 34 ms 30928 KB Output is correct
27 Correct 40 ms 32500 KB Output is correct
28 Correct 34 ms 32720 KB Output is correct
29 Correct 43 ms 35732 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15208 KB Output is correct
3 Correct 3 ms 15448 KB Output is correct
4 Correct 3 ms 15568 KB Output is correct
5 Correct 3 ms 15448 KB Output is correct
6 Correct 3 ms 15452 KB Output is correct
7 Correct 3 ms 15452 KB Output is correct
8 Correct 3 ms 15452 KB Output is correct
9 Correct 3 ms 15504 KB Output is correct
10 Correct 2 ms 15248 KB Output is correct
11 Correct 2 ms 15416 KB Output is correct
12 Correct 2 ms 15248 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 12 ms 22496 KB Output is correct
15 Correct 22 ms 27868 KB Output is correct
16 Correct 36 ms 33232 KB Output is correct
17 Correct 47 ms 38756 KB Output is correct
18 Correct 46 ms 38864 KB Output is correct
19 Correct 48 ms 38864 KB Output is correct
20 Correct 47 ms 38864 KB Output is correct
21 Correct 45 ms 39292 KB Output is correct
22 Correct 32 ms 31948 KB Output is correct
23 Correct 31 ms 29052 KB Output is correct
24 Correct 27 ms 26488 KB Output is correct
25 Correct 36 ms 33616 KB Output is correct
26 Correct 34 ms 30928 KB Output is correct
27 Correct 40 ms 32500 KB Output is correct
28 Correct 34 ms 32720 KB Output is correct
29 Correct 43 ms 35732 KB Output is correct
30 Correct 98 ms 55496 KB Output is correct
31 Correct 140 ms 73408 KB Output is correct
32 Correct 184 ms 92096 KB Output is correct
33 Correct 301 ms 132532 KB Output is correct
34 Correct 94 ms 51904 KB Output is correct
35 Correct 292 ms 132572 KB Output is correct
36 Correct 286 ms 131676 KB Output is correct
37 Correct 289 ms 131512 KB Output is correct
38 Correct 278 ms 133044 KB Output is correct
39 Correct 288 ms 132792 KB Output is correct
40 Correct 273 ms 135608 KB Output is correct
41 Correct 290 ms 131512 KB Output is correct
42 Correct 291 ms 130604 KB Output is correct
43 Correct 211 ms 133080 KB Output is correct
44 Correct 215 ms 134324 KB Output is correct
45 Correct 211 ms 135092 KB Output is correct
46 Correct 161 ms 79872 KB Output is correct
47 Correct 159 ms 61108 KB Output is correct
48 Correct 206 ms 100020 KB Output is correct
49 Correct 207 ms 100440 KB Output is correct