Submission #488320

#TimeUsernameProblemLanguageResultExecution timeMemory
488320lukameladzeFortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
1 ms460 KiB
# include <bits/stdc++.h> #define f first #define s second #define pb push_back #define int long long #define pii pair <int, int> using namespace std; const int N = 3e5 + 5; int n,k,a[N],b[N],cnt, x[N],curj,aa,bb,mn,mx,frmt,frm,idd,ans; vector <pii>v; vector <pii> v1,v2; int tree[4*N],tree1[N]; multiset <int> ms; multiset <int> :: iterator it; map <int, int > idx; void upd(int idx, int val) { for (int i = idx; i < N; i += i&(-i)) { tree1[i] += val; } } int get1(int idx) { int pas = 0; for (int i = idx; i > 0 ; i -= i&(-i)) { pas += tree1[i]; } return pas; } int get(int le, int ri) { return get1(ri) - get1(le - 1); } void update(int node, int le, int ri, int idx, int val) { if (le > idx || ri < idx) { return ; } if (le == ri) { tree[node] = max(tree[node],val); return ; } int mid = (le + ri) / 2; update(2*node, le, mid,idx,val); update(2*node + 1, mid + 1, ri, idx, val); tree[node] = max(tree[2*node],tree[2*node + 1]); } int getans(int node, int le, int ri, int start, int end) { if (le > end || ri < start) return 0; if (le >= start && ri <= end) { return tree[node]; } int mid = (le + ri) / 2; return max(getans(2*node, le, mid, start,end), getans(2*node + 1, mid + 1, ri, start,end)); } main() { cin>>n>>k; for (int i = 1; i <= n; i++) { cin>>a[i]>>b[i]; v.pb({max(a[i],b[i]),i}); } for (int i = 1; i <= k; i++) { cin>>x[i]; v1.pb({x[i],i}); v2.pb({x[i],i}); ms.insert(x[i]); } ms.insert(1e9 + 1); sort(v.begin(),v.end());reverse(v.begin(),v.end()); sort(v1.begin(),v1.end()); reverse(v1.begin(), v1.end()); v2.pb({1e9 + 1, 1}); sort(v2.begin(),v2.end()); idx[v2[0].f] = 1; cnt = 1; for (int i = 1; i < v2.size(); i++) { if (v2[i].f != v2[i - 1].f) cnt++; idx[v2[i].f] = cnt; } for (int i = 0; i < (int)v2.size() - 1; i++) { update(1,1,k,idx[v2[i].f], v2[i].s); } curj = 0; for (int i = 0; i < v.size(); i++) { while(curj < v1.size() && v1[curj].f >= v[i].f) { upd(v1[curj].s,1); curj++; } aa = a[v[i].s]; bb = b[v[i].s]; mn = min(aa,bb); mx = max(aa,bb); it = ms.lower_bound(mn); frmt = idx[*it]; it = ms.lower_bound(mx); frm = idx[(*it)] - 1; idd = 0; if (frmt <= frm) { idd = getans(1,1,k,frmt,frm); if (idd != 0) aa = mx, bb = mn; } if (get(idd + 1, n) % 2 == 1) swap(aa,bb); ans += aa; } cout<<ans<<"\n"; }

Compilation message (stderr)

fortune_telling2.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 1; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
fortune_telling2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
fortune_telling2.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   while(curj < v1.size() && v1[curj].f >= v[i].f) {
      |         ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...