Submission #758080

#TimeUsernameProblemLanguageResultExecution timeMemory
758080PoPularPlusPlusFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
234 ms17720 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pb(e) push_back(e) #define sv(a) sort(a.begin(),a.end()) #define sa(a,n) sort(a,a+n) #define mp(a,b) make_pair(a,b) #define vf first #define vs second #define ar array #define all(x) x.begin(),x.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const double PI=3.14159265358979323846264338327950288419716939937510582097494459230; mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); bool remender(ll a , ll b){return a%b;} //freopen("problemname.in", "r", stdin); //freopen("problemname.out", "w", stdout); struct Seg { int siz; vector<int> mx; void init(int n){ siz = 1; while(siz < n)siz *= 2; mx.assign(siz * 2 , -1); } void build(vector<int>& a , int x , int lx , int rx){ if(rx - lx == 1){ if(lx < a.size())mx[x] = a[lx]; return; } int m = (lx + rx)/2; build(a , 2 * x + 1 , lx , m); build(a , 2 * x + 2 , m , rx); mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]); } void build(vector<int>& a){ build(a , 0 , 0 , siz); } int range_mx(int l , int r , int x , int lx ,int rx){ if(r <= lx || rx <= l)return -1; if(lx >= l && rx <= r)return mx[x]; int m = (lx + rx)/2; return max(range_mx(l , r , 2 * x + 1 , lx , m) , range_mx(l , r , 2 * x + 2 , m ,rx)); } int range_mx(int l , int r){ return range_mx(l , r , 0 , 0 , siz); } }; struct Fen { vector<int> tree; int n; void init(int n1){ n = n1; tree.assign(n + 1 , 0); } void set(int i){ i++; while(i <= n){ tree[i]++; i += (i & -i); } } int sum(int i){ i++; int res = 0; while(i > 0){ res += tree[i]; i -= (i & -i); } return res; } }; void solve(){ int n , k; cin >> n >> k; int arr[n][2]; for(int i = 0; i < n; i++)cin >> arr[i][0] >> arr[i][1]; vector<pair<int,int>> q; for(int i = 0; i < k; i++){ int x; cin >> x; q.pb(mp(x,i)); } sort(all(q)); vector<int> a,b; for(int i = 0; i < k; i++){ if(i == k - 1 || q[i+1].vf != q[i].vf){ a.pb(q[i].vf); b.pb(q[i].vs); } } Seg st; st.init(b.size() + 1); st.build(b); //cout << "came" << endl; int pos[n]; ll res = 0; for(int i = 0; i < n; i++){ if(arr[i][0] == arr[i][1]){ res += arr[i][0]; continue; } int l = lower_bound(all(a),min(arr[i][0],arr[i][1])) - a.begin(); int r = lower_bound(all(a),max(arr[i][0],arr[i][1])) - a.begin(); if(l == r){ pos[i] = -1; } else pos[i] = st.range_mx(l , r); } vector<pair<int,int>> v; for(int i = 0; i < n; i++){ if(arr[i][0] != arr[i][1])v.pb(mp(max(arr[i][0] , arr[i][1]),i)); } sort(all(v),greater<>()); Fen ft; ft.init(k + 1); int j = q.size() - 1; int cnt = 0; for(int i = 0; i < v.size(); i++){ while(j >= 0 && q[j].vf >= v[i].vf){ ft.set(q[j].vs); j--; cnt++; } int idx = v[i].vs; if(pos[idx] == k-1){ //cout << v[i].vf << ' '; res += v[i].vf; continue; } if(pos[idx] == -1){ if(cnt % 2 == 0){ res += arr[idx][0]; //cout << arr[idx][0] << ' '; } else { res += arr[idx][1]; //cout << arr[idx][1] << ' '; } continue; } int sub = ft.sum(pos[idx]); //cout << "sub " << sub << ' '; if((cnt - sub) % 2 == 0){ //cout << v[i].vf << ' '; res += v[i].vf; } else { res += min(arr[idx][0] , arr[idx][1]); //cout << min(arr[idx][0] , arr[idx][1]) << ' '; } } cout << res << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); //int t;cin >> t;while(t--) solve(); return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void Seg::build(std::vector<int>&, int, int, int)':
fortune_telling2.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(lx < a.size())mx[x] = a[lx];
      |       ~~~^~~~~~~~~~
fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...