oj.uz

Submission #524805

# Submission time Handle Problem Language Result Execution time Memory
524805 2022-02-10T04:58:43 Z SmolBrain Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 274 ms 53988 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct sparse_table{
    /*============================*/

    T merge(T a, T b){
        return max(a, b);
    }

    /*============================*/

    vector<vector<T>> table;
    vector<int> bin_log;
    int LOG = 0;

    sparse_table(){

    }
    
    sparse_table(vector<T> &a, int n){
        while((1 << LOG) <= n) LOG++;

        table = vector<vector<T>>(n, vector<T>(LOG));
        bin_log = vector<int>(n+1);

        rep(i,n) table[i][0] = a[i];
        
        rep1(j,LOG-1){
            rep(i,n){
                int jump = 1 << (j - 1);
                if(i + jump >= n){
                    break;
                }

                table[i][j] = merge(table[i][j-1], table[i + jump][j-1]);
            }
        }

        bin_log[1] = 0;
        for(int i = 2; i <= n; ++i){
            bin_log[i] = bin_log[i/2] + 1;
        }
    }

    T query(int l, int r){
        int len = r - l + 1;
        int k = bin_log[len];

        T val1 = table[l][k];
        T val2 = table[r - (1 << k) + 1][k];

        return merge(val1, val2);
    }
};

template<typename T>
struct fenwick{
    int siz;
    vector<T> tree;
    
    fenwick(int n){
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x){
        return __builtin_ffs(x) - 1;
    }

    void build(vector<T> &a, int n){
        for(int i = 1; i <= n; ++i){
            int toadd = 1 << lsb(i);
            int par = i + toadd;
            tree[i] += a[i];

            if(par <= siz){
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v){
        while(i <= siz){
            tree[i] += v;
            int toadd = 1 << lsb(i);
            i += toadd;
        }
    }

    T sum(int i){
        T res = 0;

        while(i){
            res += tree[i];
            int tosub = 1 << lsb(i);
            i -= tosub;
        }

        return res;
    }

    T query(int l, int r){
        T res = sum(r) - sum(l-1);
        return res;
    }
};

void solve(int test_case)
{
    // https://blog.naver.com/jh05013/221306447912
    ll n, k; cin >> n >> k;
    vector<pair<ll, ll>> a(n), b(k);
    rep(i, n) cin >> a[i].ff >> a[i].ss;
    rep(i, k) {
        ll x; cin >> x;
        b[i] = {x, i};
    }

    auto comp = [&](pair<ll, ll> &p1, pair<ll, ll> &p2) {
        return max(p1.ff, p1.ss) > max(p2.ff, p2.ss);
    };

    sort(all(a), comp);
    sort(all(b));

    vector<ll> c(k), d(k);
    rep(i, k) c[i] = b[i].ff, d[i] = b[i].ss;

    sparse_table<ll> st(d, k);
    fenwick<ll> fenw(k + 5);

    ll ptr = k - 1;
    ll ans = 0;

    rep(i, n) {
        ll flip = 0;

        if (a[i].ff < a[i].ss) {
            swap(a[i].ff, a[i].ss);
            flip = 1;
        }

        while (ptr >= 0 and b[ptr].ff >= a[i].ff) {
            // fenwick only works for 1-indexed values
            fenw.pupd(b[ptr].ss + 1, 1);
            ptr--;
        }

        ll l = lower_bound(all(c), a[i].ss) - c.begin();
        ll r = lower_bound(all(c), a[i].ff) - c.begin() - 1;

        ll mx = 0;
        if(l < k and l <= r){
            flip = 0;
            mx = st.query(l, r);
        }

        flip += fenw.query(mx + 1, k);
        flip %= 2;

        if(!flip){
            ans += a[i].ff;
        }
        else{
            ans += a[i].ss;
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void usaco(std::string)':
fortune_telling2.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:59:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 9 ms 2636 KB Output is correct
15 Correct 18 ms 4992 KB Output is correct
16 Correct 30 ms 7532 KB Output is correct
17 Correct 42 ms 10408 KB Output is correct
18 Correct 39 ms 10304 KB Output is correct
19 Correct 40 ms 10504 KB Output is correct
20 Correct 36 ms 10388 KB Output is correct
21 Correct 33 ms 10388 KB Output is correct
22 Correct 27 ms 9924 KB Output is correct
23 Correct 27 ms 9884 KB Output is correct
24 Correct 28 ms 9868 KB Output is correct
25 Correct 26 ms 9928 KB Output is correct
26 Correct 28 ms 10176 KB Output is correct
27 Correct 32 ms 10296 KB Output is correct
28 Correct 31 ms 10308 KB Output is correct
29 Correct 33 ms 10376 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 9 ms 2636 KB Output is correct
15 Correct 18 ms 4992 KB Output is correct
16 Correct 30 ms 7532 KB Output is correct
17 Correct 42 ms 10408 KB Output is correct
18 Correct 39 ms 10304 KB Output is correct
19 Correct 40 ms 10504 KB Output is correct
20 Correct 36 ms 10388 KB Output is correct
21 Correct 33 ms 10388 KB Output is correct
22 Correct 27 ms 9924 KB Output is correct
23 Correct 27 ms 9884 KB Output is correct
24 Correct 28 ms 9868 KB Output is correct
25 Correct 26 ms 9928 KB Output is correct
26 Correct 28 ms 10176 KB Output is correct
27 Correct 32 ms 10296 KB Output is correct
28 Correct 31 ms 10308 KB Output is correct
29 Correct 33 ms 10376 KB Output is correct
30 Correct 138 ms 47248 KB Output is correct
31 Correct 165 ms 48604 KB Output is correct
32 Correct 208 ms 50376 KB Output is correct
33 Correct 274 ms 53888 KB Output is correct
34 Correct 105 ms 46788 KB Output is correct
35 Correct 272 ms 53988 KB Output is correct
36 Correct 266 ms 53820 KB Output is correct
37 Correct 272 ms 53828 KB Output is correct
38 Correct 234 ms 53924 KB Output is correct
39 Correct 233 ms 53816 KB Output is correct
40 Correct 198 ms 53560 KB Output is correct
41 Correct 206 ms 53804 KB Output is correct
42 Correct 235 ms 53868 KB Output is correct
43 Correct 162 ms 53160 KB Output is correct
44 Correct 164 ms 53156 KB Output is correct
45 Correct 153 ms 53104 KB Output is correct
46 Correct 184 ms 52004 KB Output is correct
47 Correct 185 ms 51744 KB Output is correct
48 Correct 194 ms 53952 KB Output is correct
49 Correct 189 ms 53888 KB Output is correct