oj.uz

Submission #516523

# Submission time Handle Problem Language Result Execution time Memory
516523 2022-01-21T12:45:58 Z MilosMilutinovic Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 205 ms 100592 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[400005];
	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[4000005],rc[4000005],st[4000005],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 444 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 2 ms 576 KB Output is correct
13 Correct 2 ms 592 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 444 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 2 ms 576 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 22 ms 3036 KB Output is correct
15 Correct 31 ms 6016 KB Output is correct
16 Correct 49 ms 9272 KB Output is correct
17 Correct 83 ms 12084 KB Output is correct
18 Correct 64 ms 12140 KB Output is correct
19 Correct 67 ms 12144 KB Output is correct
20 Correct 61 ms 12136 KB Output is correct
21 Correct 66 ms 12104 KB Output is correct
22 Correct 47 ms 11312 KB Output is correct
23 Correct 48 ms 10644 KB Output is correct
24 Correct 63 ms 10428 KB Output is correct
25 Correct 47 ms 11540 KB Output is correct
26 Correct 54 ms 11544 KB Output is correct
27 Correct 62 ms 11844 KB Output is correct
28 Correct 51 ms 11840 KB Output is correct
29 Correct 96 ms 12024 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 2 ms 576 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 22 ms 3036 KB Output is correct
15 Correct 31 ms 6016 KB Output is correct
16 Correct 49 ms 9272 KB Output is correct
17 Correct 83 ms 12084 KB Output is correct
18 Correct 64 ms 12140 KB Output is correct
19 Correct 67 ms 12144 KB Output is correct
20 Correct 61 ms 12136 KB Output is correct
21 Correct 66 ms 12104 KB Output is correct
22 Correct 47 ms 11312 KB Output is correct
23 Correct 48 ms 10644 KB Output is correct
24 Correct 63 ms 10428 KB Output is correct
25 Correct 47 ms 11540 KB Output is correct
26 Correct 54 ms 11544 KB Output is correct
27 Correct 62 ms 11844 KB Output is correct
28 Correct 51 ms 11840 KB Output is correct
29 Correct 96 ms 12024 KB Output is correct
30 Runtime error 205 ms 100592 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -