oj.uz

Submission #516526

# Submission time Handle Problem Language Result Execution time Memory
516526 2022-01-21T12:47:14 Z MilosMilutinovic Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 463 ms 67532 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q;
int a[200005],b[200005],x[200005];

namespace cpr{
	vector<int> v;
	void add(int x){ v.pb(x); }
	void build(){
		sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
	}
	int get(int x){
		return lower_bound(v.begin(),v.end(),x)-v.begin();
	}
};

namespace sgt1{
	int maxa[3000005];
	void change(int id,int l,int r,int qi,int c){
		if(l==r) return (void)(maxa[id]=max(maxa[id],c));
		int mid=(l+r)/2;
		if(qi<=mid) change(id<<1,l,mid,qi,c);
		else change(id<<1|1,mid+1,r,qi,c);
		maxa[id]=max(maxa[id<<1],maxa[id<<1|1]);
	}
	int query(int id,int l,int r,int ql,int qr){
		if(ql>qr||l>qr||r<ql) return 0;
		if(ql<=l&&r<=qr) return maxa[id];
		int mid=(l+r)/2;
		return max(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
	}
};

namespace psgt{
	int root[200005],lc[8000005],rc[8000005],st[8000005],tsz;
	void change(int&id,int p,int l,int r,int qi){
		id=++tsz; lc[id]=lc[p]; rc[id]=rc[p]; st[id]=st[p]+1;
		if(l==r) return;
		int mid=(l+r)/2;
		if(qi<=mid) change(lc[id],lc[p],l,mid,qi);
		else change(rc[id],rc[p],mid+1,r,qi);
	}
	int query(int id,int l,int r,int ql,int qr){
		if(l>qr||r<ql) return 0;
		if(ql<=l&&r<=qr) return st[id];
		int mid=(l+r)/2;
		return query(lc[id],l,mid,ql,qr)+query(rc[id],mid+1,r,ql,qr);
	}
	int query(int i,int l,int r){ return query(root[i],0,m-1,l,r); }
	void update(int i,int x){ change(root[i],root[i+1],0,m-1,x); }
};

int main(){
	n=readint(); q=readint();
	for(int i=1;i<=n;i++) a[i]=readint(),b[i]=readint();
	for(int i=1;i<=q;i++) x[i]=readint();
	for(int i=1;i<=n;i++) cpr::add(a[i]),cpr::add(b[i]);
	for(int i=1;i<=q;i++) cpr::add(x[i]);
	cpr::build();
	m=cpr::v.size();
	for(int i=1;i<=n;i++) a[i]=cpr::get(a[i]),b[i]=cpr::get(b[i]);
	for(int i=1;i<=q;i++) x[i]=cpr::get(x[i]);
	for(int i=1;i<=q;i++) sgt1::change(1,0,m-1,x[i],i);
	for(int i=q;i>=1;i--) psgt::update(i,x[i]);
	ll ans=0;
	for(int i=1;i<=n;i++){
		int mn=min(a[i],b[i]),mx=max(a[i],b[i]);
		int id=sgt1::query(1,0,m-1,mn,mx-1);
		int cnt=psgt::query(id+1,mx,m-1);
		if(id!=0) a[i]=mx,b[i]=mn;
		if(cnt&1) swap(a[i],b[i]);
		ans+=cpr::v[a[i]];
	}
	printf("%lld\n",ans);
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 14 ms 2868 KB Output is correct
15 Correct 29 ms 5460 KB Output is correct
16 Correct 46 ms 8516 KB Output is correct
17 Correct 71 ms 10980 KB Output is correct
18 Correct 67 ms 10988 KB Output is correct
19 Correct 64 ms 10988 KB Output is correct
20 Correct 61 ms 10980 KB Output is correct
21 Correct 62 ms 10988 KB Output is correct
22 Correct 48 ms 10684 KB Output is correct
23 Correct 48 ms 9972 KB Output is correct
24 Correct 52 ms 9876 KB Output is correct
25 Correct 54 ms 10860 KB Output is correct
26 Correct 47 ms 10548 KB Output is correct
27 Correct 64 ms 10732 KB Output is correct
28 Correct 53 ms 10680 KB Output is correct
29 Correct 83 ms 10884 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 14 ms 2868 KB Output is correct
15 Correct 29 ms 5460 KB Output is correct
16 Correct 46 ms 8516 KB Output is correct
17 Correct 71 ms 10980 KB Output is correct
18 Correct 67 ms 10988 KB Output is correct
19 Correct 64 ms 10988 KB Output is correct
20 Correct 61 ms 10980 KB Output is correct
21 Correct 62 ms 10988 KB Output is correct
22 Correct 48 ms 10684 KB Output is correct
23 Correct 48 ms 9972 KB Output is correct
24 Correct 52 ms 9876 KB Output is correct
25 Correct 54 ms 10860 KB Output is correct
26 Correct 47 ms 10548 KB Output is correct
27 Correct 64 ms 10732 KB Output is correct
28 Correct 53 ms 10680 KB Output is correct
29 Correct 83 ms 10884 KB Output is correct
30 Correct 164 ms 49148 KB Output is correct
31 Correct 219 ms 52848 KB Output is correct
32 Correct 276 ms 58524 KB Output is correct
33 Correct 410 ms 67376 KB Output is correct
34 Correct 153 ms 50616 KB Output is correct
35 Correct 447 ms 67504 KB Output is correct
36 Correct 396 ms 67404 KB Output is correct
37 Correct 439 ms 67384 KB Output is correct
38 Correct 411 ms 67408 KB Output is correct
39 Correct 445 ms 67428 KB Output is correct
40 Correct 463 ms 67248 KB Output is correct
41 Correct 456 ms 67480 KB Output is correct
42 Correct 402 ms 67532 KB Output is correct
43 Correct 296 ms 62760 KB Output is correct
44 Correct 306 ms 63084 KB Output is correct
45 Correct 296 ms 63820 KB Output is correct
46 Correct 316 ms 59140 KB Output is correct
47 Correct 257 ms 55560 KB Output is correct
48 Correct 318 ms 62032 KB Output is correct
49 Correct 307 ms 62308 KB Output is correct