Submission #952876

#TimeUsernameProblemLanguageResultExecution timeMemory
952876CLC__HaalandFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
4 ms21336 KiB
#include <bits/stdc++.h> #define se second #define fs first #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for (auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 2e5 + 7; const int Mod = 1e9 + 7; const int szBL = 500; const int INF = 2e9 + 7; const int BASE = 137; struct Arr_Data { int a, b; bool isswapped; Arr_Data () : a(0), b(0), isswapped(0) {}; }; ///input: int n, Q; Arr_Data arr[N]; int qr[N]; ///compress: int num_Val; vector<int> nen; int CPR (int X) { return lower_bound(ALL(nen), X) - nen.begin() + 1; } void compress () { sort (ALL(nen)); nen.resize(num_Val = unique(ALL(nen)) - nen.begin()); rep (i, 1, n) { arr[i].a = CPR(arr[i].a); arr[i].b = CPR(arr[i].b); } rep (i, 1, Q) qr[i] = CPR(qr[i]); } ///data: vector<vector<int>> queries, events; namespace sub3 { struct Segment_Tree_helper1 { int Range; int st[3][N << 2]; void init(int n ) { Range = n; rep (i, 0, (Range + 1) << 2) st[0][i] = INF, st[1][i] = 0, st[0][i] = 0; } void update (int id, int l, int r, int pos, int val) { if (l > pos || r < pos) return; if (l == r) { st[1][id] = st[0][id] = st[2][id] = val; return; } int mid = l + r >> 1; update (id << 1, l, mid, pos, val); update (id << 1 | 1, mid + 1, r, pos, val); st[0][id] = min(st[0][id << 1], st[0][id << 1 | 1]); st[1][id] = max(st[1][id << 1], st[1][id << 1 | 1]); st[2][id] = st[2][id << 1] + st[2][id << 1 | 1]; } int get (int id, int l, int r, int u, int v, int typ) { if (l > v || r < u) { if (typ == 0) return INF; else return 0; } if (l >= u && r <= v) return st[typ][id]; int mid = l + r >> 1; if (typ == 1) return max(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ)); else if (typ == 0) return min(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ)); else if (typ == 2) return get (id << 1, l, mid, u, v, typ) + get (id << 1 | 1, mid + 1, r, u, v, typ); } int walk_Left (int id, int l, int r, int bound) { ///walk to Find L when the upper_bound is bound if (l > bound) return -1; if (st[1][id] == 0) return -1; if (l == r) return l; int mid = l + r >> 1; int res = -1; if (mid + 1 <= bound) res = walk_Left (id << 1 | 1 , mid + 1, r, bound); if (res == -1) res = walk_Left (id << 1, l, mid, bound); return res; } int walk_Right (int id, int l, int r, int bound) { ///walk to Find R when the lower_bound is bound if (r < bound) return -1; if (st[1][id] == 0) return -1; if (l == r) return l; int mid = l + r >> 1; int res = -1; if (mid >= bound) res = walk_Right (id << 1, l, mid, bound); if (res == -1) res = walk_Right (id << 1 | 1, mid + 1, r, bound); return res; } int search_smallest_pole (int id, int l, int r, int bound) { ///value need to strictly smaller the bound if (st[0][id] >= bound) return -1; if (l == r) return l; int mid = l + r >> 1; int res = -1; if (st[0][id << 1 | 1] < bound) { res = search_smallest_pole(id << 1, l, mid, bound); if (res == -1) search_smallest_pole (id << 1 | 1, mid + 1, r, bound); } return res; } void update (int pos, int val) { update (1, 0, Range, pos, val); } int getMx (int L, int R) { return get (1, 0, Range, L, R, 1); } int getMn (int L, int R) { return get (1, 0, Range, L, R, 0); } int Sum (int L, int R) { return get (1, 0, Range, L, R, 2); } int walk_Left (int bound){ return walk_Left (1, 0, Range, bound); } int walk_Right (int bound) { return walk_Right (1, 0, Range, bound); } int search_smallest_pole (int bound) { return search_smallest_pole (1, 0, Range, bound); } }ST, Partition, values_Range; void solution() { nen = {0, INF}; rep (i, 1, n) nen.push_back(arr[i].a), nen.push_back(arr[i].b); rep (i, 1, Q) nen.push_back(qr[i]); compress(); events.resize(num_Val + 1, vector<int> (0)); queries.resize(num_Val + 1, vector<int> (0)); rep (i, 1, n) { if (arr[i].a > arr[i].b) { swap(arr[i].a, arr[i].b); arr[i].isswapped = 1; } events[arr[i].b].push_back(i); } rep (i, 1, Q) queries[qr[i]].push_back(i); ST.init(Q), Partition.init(Q), values_Range.init(Q); rep (i, 1, Q) ST.update(i, qr[i]); values_Range.update (0, ST.getMx(1, Q)); ///set stored maximum value of each range vector<int> final_arr(n + 1, 0); reb (X, num_Val, 1) { iter (&id, queries[X]) { int boundL = Partition.walk_Left(id - 1), boundR = Partition.walk_Right(id + 1); if (boundL == -1) boundL = 0; if (boundR == -1) boundR = Q + 1; Partition.update (id, 1); values_Range.update (id, ST.getMx(id + 1, boundR - 1)); ///dont need to consider the edgecase values_Range.update (boundL, ST.getMx(boundL + 1, id - 1)); } iter (&id, events[X]) { int A = arr[id].a, B = arr[id].b, swapped = arr[id].isswapped; int smallest_idx = values_Range.search_smallest_pole(arr[id].a); if (smallest_idx == -1) smallest_idx = Q + 1; // cout <<"183: "<<id<<": "<<smallest_idx<<" "<<"\n"; int parity = Partition.Sum(smallest_idx, Q) % 2; if (swapped) { if (smallest_idx == 0) parity ^= 1; } if (parity & 1) final_arr[id] = B; else final_arr[id] = A; } } ll res = 0; rep (i, 1, n) { // cout << nen[final_arr[i] - 1] << " "; res += nen[final_arr[i] - 1]; } cout << res <<"\n"; } } void solution() { cin >> n >> Q; rep (i, 1, n) { cin >> arr[i].a >> arr[i].b; } rep (i, 1, Q) cin >> qr[i]; sub3 :: solution(); } #define file(name) freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); int main() { // file("c"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) solution(); } /* 4 4 aaab 1 4 1 3 3 4 2 4 */

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void sub3::Segment_Tree_helper1::update(int, int, int, int, int)':
fortune_telling2.cpp:73:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:86:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Left(int, int, int, int)':
fortune_telling2.cpp:95:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Right(int, int, int, int)':
fortune_telling2.cpp:105:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::search_smallest_pole(int, int, int, int)':
fortune_telling2.cpp:115:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:90:9: warning: control reaches end of non-void function [-Wreturn-type]
   90 |         }
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...