oj.uz

Submission #708240

# Submission time Handle Problem Language Result Execution time Memory
708240 2023-03-11T11:24:20 Z Dan4Life Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 664 ms 106332 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)2e5+10, LINF = (int)1e18;

vector<int> v, w[mxN];
int n, m, q, mxSz, sum;
unordered_map<int,int> ind;
int a[mxN], b[mxN], t[mxN], orig[3*mxN], segTree[4*mxN];
template<class T> using ordered_set = tree<T,null_type, less<T>,
				rb_tree_tag,tree_order_statistics_node_update>;
					
ordered_set<pair<int,int>> S; 

void upd(int i, int v, int p=0, int l=0, int r=mxSz-1){
	if(l==r){ segTree[p]=max(segTree[p],v); return; }
	int mid = (l+r)/2; int lp = p+1, rp = p+2*(mid-l+1);
	if(i<=mid) upd(i,v,lp,l,mid);
	else upd(i,v,rp,mid+1,r);
	segTree[p] = max(segTree[lp],segTree[rp]);
}

int query(int i, int j, int p=0, int l=0, int r=mxSz-1){
	if(i>r or j<l or i>j) return 0;
	if(i<=l and r<=j) return segTree[p];
	int mid = (l+r)/2; int lp = p+1, rp = p+2*(mid-l+1);
	return max(query(i,j,lp,l,mid),query(i,j,rp,mid+1,r));
} 

main() {
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
		cin >> a[i] >> b[i], v.pb(a[i]), v.pb(b[i]);
	for(int i = 1; i <= q; i++) cin >> t[i], v.pb(t[i]);
	sort(all(v)); v.erase(unique(all(v)),v.end());
	for(mxSz = 0; auto u : v) ind[u]=mxSz++, orig[mxSz-1]=u;
	for(int i = 1; i <= n; i++) a[i]=ind[a[i]],b[i]=ind[b[i]];
	for(int i = 1; i <= q; i++) t[i]=ind[t[i]], upd(t[i],i);
	for(int i = 1; i <= n; i++)
		w[query(min(a[i],b[i]),max(a[i],b[i])-1)].pb(i);
	for(int i = q; i>=0; S.insert({t[i],i}), i--){
		for(auto j : w[i]){
			int x = a[j], y = b[j], tot = q-i;
			bool switched = (x<y); if(!i) switched=0;
			int pos = S.order_of_key({max(x,y),-1});
			//if(i==q) {sum+=max(x,y); continue;}
			pos = sz(S)-pos, switched^=pos%2;
			sum+=orig[switched?y:x];
			//cout << orig[x] << " ";
			//cout << i << " " << j << " " << pos << " " << orig[switched?y:x] << "\n";
		}
	}
	cout << sum << "\n";
}

Compilation message

fortune_telling2.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:42:16: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   42 |  for(mxSz = 0; auto u : v) ind[u]=mxSz++, orig[mxSz-1]=u;
      |                ^~~~
fortune_telling2.cpp:49:28: warning: unused variable 'tot' [-Wunused-variable]
   49 |    int x = a[j], y = b[j], tot = q-i;
      |                            ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5380 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5400 KB Output is correct
7 Correct 5 ms 5380 KB Output is correct
8 Correct 5 ms 5272 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 4 ms 5140 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 5 ms 5332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5380 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5400 KB Output is correct
7 Correct 5 ms 5380 KB Output is correct
8 Correct 5 ms 5272 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 4 ms 5140 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 5 ms 5332 KB Output is correct
14 Correct 39 ms 8440 KB Output is correct
15 Correct 57 ms 11872 KB Output is correct
16 Correct 88 ms 15748 KB Output is correct
17 Correct 123 ms 18800 KB Output is correct
18 Correct 122 ms 18860 KB Output is correct
19 Correct 152 ms 18932 KB Output is correct
20 Correct 117 ms 18852 KB Output is correct
21 Correct 125 ms 18792 KB Output is correct
22 Correct 79 ms 15532 KB Output is correct
23 Correct 85 ms 14356 KB Output is correct
24 Correct 92 ms 13580 KB Output is correct
25 Correct 87 ms 16716 KB Output is correct
26 Correct 94 ms 15264 KB Output is correct
27 Correct 114 ms 16080 KB Output is correct
28 Correct 113 ms 16060 KB Output is correct
29 Correct 116 ms 17888 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5380 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5400 KB Output is correct
7 Correct 5 ms 5380 KB Output is correct
8 Correct 5 ms 5272 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 4 ms 5140 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 5 ms 5332 KB Output is correct
14 Correct 39 ms 8440 KB Output is correct
15 Correct 57 ms 11872 KB Output is correct
16 Correct 88 ms 15748 KB Output is correct
17 Correct 123 ms 18800 KB Output is correct
18 Correct 122 ms 18860 KB Output is correct
19 Correct 152 ms 18932 KB Output is correct
20 Correct 117 ms 18852 KB Output is correct
21 Correct 125 ms 18792 KB Output is correct
22 Correct 79 ms 15532 KB Output is correct
23 Correct 85 ms 14356 KB Output is correct
24 Correct 92 ms 13580 KB Output is correct
25 Correct 87 ms 16716 KB Output is correct
26 Correct 94 ms 15264 KB Output is correct
27 Correct 114 ms 16080 KB Output is correct
28 Correct 113 ms 16060 KB Output is correct
29 Correct 116 ms 17888 KB Output is correct
30 Correct 399 ms 38128 KB Output is correct
31 Correct 485 ms 44764 KB Output is correct
32 Correct 627 ms 55920 KB Output is correct
33 Runtime error 664 ms 106332 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -