Submission #1052844

#TimeUsernameProblemLanguageResultExecution timeMemory
1052844phongFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
103 ms17216 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define ll long long const int nmax = 2e5 + 5, N = 1e6; const ll oo = 1e9 + 5, base = 311; const int lg = 17, tx = 26; const ll mod = 998244353; #define pii pair<ll, ll> #define fi first #define se second #define endl "\n" #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n"; using namespace std; int n, k; pii c[nmax]; struct node{ int first, second, id; }a[nmax]; int L[nmax]; struct SEG{ int tree[nmax << 2]; void update(int id, int l, int r, int u, int val){ if(l > u|| r < u)return; if(l >= u && r <= u){ tree[id] = val; return; } int mid = r + l >> 1; update(id << 1, l, mid, u, val); update(id << 1 | 1, mid + 1, r, u, val); tree[id] = max(tree[id << 1], tree[id << 1 | 1]); } int get(int val){ if(tree[1] < val) return 0; int id = 1, l = 1, r = k; while(l != r){ int mid = r + l >> 1; if(tree[id << 1 | 1] >= val){ id = id << 1 | 1; l = mid + 1; } else{ id = id << 1; r = mid; } } return l; } }tree; struct BIT{ int f[nmax]; void update(int u, int val){ for(; u; u -= u&-u) f[u] += val; } int get(int u){ int res = 0; for(; u <= k; u += u&-u) res += f[u]; return res; } }F; int d[nmax]; main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("code.inp", "r", stdin); // freopen("code.out", "w", stdout); cin >> n >> k; for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se, a[i].id = i; for(int i = 1; i <= k; ++i) cin >> c[i].fi, c[i].se = i, d[i] = c[i].fi; sort(a + 1, a + 1 + n, [](node a, node b){ return max(a.fi, a.se) < max(b.fi, b.se); }); sort(c + 1, c + 1 + k); int pos = 1;// for(int i = 1; i <= n; ++i){ while(pos <= k && c[pos].fi < max(a[i].fi, a[i].se)){ tree.update(1, 1, k, c[pos].se, c[pos].fi); ++pos; } L[i] = tree.get(min(a[i].fi, a[i].se)); } pos = k;// ll ans = 0; for(int i = n; i >= 1; --i){ while(pos >= 1 && c[pos].fi >= max(a[i].fi, a[i].se)){ F.update(c[pos].se, 1); --pos; } int x = L[i]; bool idx = 0; int val = F.get(L[i] + 1); if(L[i] > 0){ if(d[L[i]] >= a[i].fi){ idx = 1; } else{ idx = 0; } } if(val & 1) idx ^= 1; if(!idx) ans += a[i].fi; else ans += a[i].se; // cout << a[i].id << ' ' << val << endl; } cout << ans; } /* 2 3 1 4 4 1 2 6 5 */

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void SEG::update(int, int, int, int, int)':
fortune_telling2.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = r + l >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int SEG::get(int)':
fortune_telling2.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             int mid = r + l >> 1;
      |                       ~~^~~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:95:13: warning: unused variable 'x' [-Wunused-variable]
   95 |         int x = L[i];
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...