Submission #1199071

#TimeUsernameProblemLanguageResultExecution timeMemory
1199071InvMODFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
1 ms576 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define eb emplace_back #define vi vector<int> #define pi pair<int,int> #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) template<class T> using upq = priority_queue<T, vector<T>, greater<T>>; template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());} template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());} #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define ROF(i, a, b) for(int i = (a); i >= (b); i--) #define sumof(x) accumulate(all(x), 0ll) #define dbg(x) "[" << #x " = " << (x) << "]" #define el "\n" using ll = long long; using ld = long double; template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);} template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);} const int N = 2e5 + 5; const int MOD = 1e9 + 7; const ll INF = numeric_limits<ll>::max() / 8; /* a[i] <= b[i] Type 1: a[i] <= T[j] < b[i] -> swap only a[i] to b[i] Type 2: b[i] <= T[j] -> swap both a[i], b[i] a[i]..... Type 1.... b[i] b[i]..... Type 1.... b[i] -> we will find the last type 1 and calculate the answer */ struct SegTree{ vector<int> st; int trsz; SegTree(int n = 0): st((n << 2) | 1), trsz(n) {} void update(int id, int l, int r, int x, int p){ if(l == r){ st[id] = max(st[id], p); } else{ int m = l+r>>1; if(x <= m) update(id << 1, l, m, x, p); else update(id << 1|1, m+1, r, x, p); st[id] = max(st[id << 1], st[id << 1|1]); } } int get(int id, int l, int r, int u, int v){ if(l > v || r < u) return 0; if(l >= u && r <= v) return st[id]; int m = l+r>>1; return max(get(id << 1, l, m, u, v), get(id << 1|1, m+1, r, u, v)); } void update(int x, int p){ update(1, 0, trsz, x, p); } int query(int l, int r){ if(l > r) return 0; return get(1, 0, trsz, l, r); } }; struct IT{ vector<vi> st; int trsz; IT(int n, vector<int>& a): st((n << 2) | 1), trsz(n){ build(1, 0, n, a); } void merge_st(int id, int l, int r){ int i = 0, j = 0; while(i < sz(st[l]) && j < sz(st[r])){ if(st[l][i] < st[r][j]){ st[id].eb(st[l][i]); i++; } else{ st[id].eb(st[r][j]); j++; } } while(i < sz(st[l])) st[id].eb(st[l][i++]); while(j < sz(st[r])) st[id].eb(st[r][j++]); } void build(int id, int l, int r, vector<int>& a){ if(l == r){ st[id].eb(a[l]); } else{ int m = l+r>>1; build(id << 1, l, m, a); build(id << 1|1, m+1, r, a); merge_st(id, id << 1, id << 1|1); } } int query(int l, int r, int k){ return query(1, 0, trsz, l, r, k); } int query(int id, int l, int r, int u, int v, int k){ if(l >= u && r <= v) return (sz(st[id]) - lwrbound(st[id], k)); int m = l+r>>1; return (u <= m ? query(id << 1, l, m, u, v, k) : 0) + (v > m ? query(id << 1|1, m+1, r, u, v, k) : 0); } }; void Main() { int n,k; cin >> n >> k; vi a(n + 1), b(n + 1); FOR(i, 1, n) cin >> a[i] >> b[i]; vi Q(k + 1); FOR(i, 1, k) cin >> Q[i]; vi comp(1, -1); FOR(i, 1, k) comp.eb(Q[i]); sort(all(comp)), compact(comp); SegTree st(sz(comp)); IT tr(k, Q); FOR(i, 1, k){ Q[i] = lwrbound(comp, Q[i]); st.update(Q[i], i); } auto brute = [&](int i) -> int{ int cur = a[i], t = 0; for(int j = 1; j <= k; j++){ if(comp[Q[j]] >= cur){ if(!t) cur = b[i]; else cur = a[i]; t ^= 1; } } return cur; }; ll ans = 0; FOR(i, 1, n){ if(a[i] > b[i]) swap(a[i], b[i]); int x = lwrbound(comp, a[i]); int y = lwrbound(comp, b[i]); int lst = st.query(x, y - 1); int change = tr.query(lst + 1, n, b[i]); ans += (((change & 1) ^ (!lst)) ? a[i] : b[i]); } cout << ans << el; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout); } int t = 1; while(t--) Main(); return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...