Submission #524795

#TimeUsernameProblemLanguageResultExecution timeMemory
524795SmolBrainFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
1 ms716 KiB
#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(rall(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); ll ptr = 0; ll ans = 0; rep(i, n) { if (a[i].ff < a[i].ss) { swap(a[i].ff, a[i].ss); } while (ptr < k and b[k].ff >= a[i].ff) { // fenwick only works for 1-indexed values fenw.pupd(b[i].ss + 1, 1); ptr++; } ll l = lower_bound(all(c), a[i].ss, greater<ll>()) - c.begin(); ll r = upper_bound(all(c), a[i].ff, greater<ll>()) - c.begin() - 1; ll mx = 0; if(l < k){ mx = st.query(l, r); } ll flip = fenw.query(mx + 1, k) & 1; 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 (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...