Submission #708245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708245	2023-03-11T11:37:07 Z	Dan4Life	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	859 ms	61008 KB

fortune_telling2

#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];
int orig[3*mxN], fenwick[3*mxN+10], segTree[6*mxN];

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));
} 

void upd2(int x, int v){ for(;x<=3*mxN; x+=x&-x) fenwick[x]+=v; }

int sum2(int x){ int s=0;for(;x;x-=x&-x) s+=fenwick[x]; return s; }
int sum2(int l, int r){
	if(l>r) return 0;
	return sum2(r)-sum2(l-1);
}

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; upd2(t[i--]+1,1)){
		for(auto j : w[i]){
			int x = a[j], y = b[j];
			bool switched = (x<y and i)^((sum2(max(x,y)+1,3*mxN))%2);
			sum+=orig[switched?y:x];
		}
	}
	cout << sum << "\n";
}

Compilation message

fortune_telling2.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:47:16: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   47 |  for(mxSz = 0; auto u : v) ind[u]=mxSz++, orig[mxSz-1]=u;
      |                ^~~~

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	6 ms	5200 KB	Output is correct
3	Correct	5 ms	5332 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	5332 KB	Output is correct
7	Correct	5 ms	5300 KB	Output is correct
8	Correct	5 ms	5296 KB	Output is correct
9	Correct	5 ms	5332 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	6 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	6 ms	5204 KB	Output is correct

Subtask #2
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	6 ms	5200 KB	Output is correct
3	Correct	5 ms	5332 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	5332 KB	Output is correct
7	Correct	5 ms	5300 KB	Output is correct
8	Correct	5 ms	5296 KB	Output is correct
9	Correct	5 ms	5332 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	6 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	6 ms	5204 KB	Output is correct
14	Correct	32 ms	7764 KB	Output is correct
15	Correct	76 ms	10616 KB	Output is correct
16	Correct	99 ms	13724 KB	Output is correct
17	Correct	111 ms	16240 KB	Output is correct
18	Correct	117 ms	16280 KB	Output is correct
19	Correct	106 ms	16284 KB	Output is correct
20	Correct	113 ms	16220 KB	Output is correct
21	Correct	109 ms	16508 KB	Output is correct
22	Correct	68 ms	12980 KB	Output is correct
23	Correct	65 ms	11840 KB	Output is correct
24	Correct	60 ms	10904 KB	Output is correct
25	Correct	76 ms	14784 KB	Output is correct
26	Correct	91 ms	12280 KB	Output is correct
27	Correct	104 ms	13168 KB	Output is correct
28	Correct	88 ms	12996 KB	Output is correct
29	Correct	97 ms	14964 KB	Output is correct

Subtask #3
65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	6 ms	5200 KB	Output is correct
3	Correct	5 ms	5332 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	5332 KB	Output is correct
7	Correct	5 ms	5300 KB	Output is correct
8	Correct	5 ms	5296 KB	Output is correct
9	Correct	5 ms	5332 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	6 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	6 ms	5204 KB	Output is correct
14	Correct	32 ms	7764 KB	Output is correct
15	Correct	76 ms	10616 KB	Output is correct
16	Correct	99 ms	13724 KB	Output is correct
17	Correct	111 ms	16240 KB	Output is correct
18	Correct	117 ms	16280 KB	Output is correct
19	Correct	106 ms	16284 KB	Output is correct
20	Correct	113 ms	16220 KB	Output is correct
21	Correct	109 ms	16508 KB	Output is correct
22	Correct	68 ms	12980 KB	Output is correct
23	Correct	65 ms	11840 KB	Output is correct
24	Correct	60 ms	10904 KB	Output is correct
25	Correct	76 ms	14784 KB	Output is correct
26	Correct	91 ms	12280 KB	Output is correct
27	Correct	104 ms	13168 KB	Output is correct
28	Correct	88 ms	12996 KB	Output is correct
29	Correct	97 ms	14964 KB	Output is correct
30	Correct	295 ms	25108 KB	Output is correct
31	Correct	407 ms	31860 KB	Output is correct
32	Correct	526 ms	43200 KB	Output is correct
33	Correct	813 ms	59968 KB	Output is correct
34	Correct	232 ms	23460 KB	Output is correct
35	Correct	849 ms	60028 KB	Output is correct
36	Correct	859 ms	59832 KB	Output is correct
37	Correct	804 ms	59684 KB	Output is correct
38	Correct	769 ms	59920 KB	Output is correct
39	Correct	810 ms	59600 KB	Output is correct
40	Correct	719 ms	61008 KB	Output is correct
41	Correct	752 ms	59556 KB	Output is correct
42	Correct	803 ms	59460 KB	Output is correct
43	Correct	536 ms	54052 KB	Output is correct
44	Correct	570 ms	54800 KB	Output is correct
45	Correct	573 ms	57008 KB	Output is correct
46	Correct	386 ms	38316 KB	Output is correct
47	Correct	329 ms	31732 KB	Output is correct
48	Correct	588 ms	47280 KB	Output is correct
49	Correct	593 ms	47836 KB	Output is correct

Submission #708245

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0