oj.uz

답안 #516525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516525 2022-01-21T12:46:42 Z MilosMilutinovic 운세 보기 2 (JOI14_fortune_telling2) C++14
35 / 100
 227 ms 107980 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[800005];
	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

# 결과 실행 시간 메모리 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 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 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 1 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

# 결과 실행 시간 메모리 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 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 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 1 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 2880 KB Output is correct
15 Correct 30 ms 5392 KB Output is correct
16 Correct 47 ms 8456 KB Output is correct
17 Correct 77 ms 10980 KB Output is correct
18 Correct 62 ms 10916 KB Output is correct
19 Correct 62 ms 10936 KB Output is correct
20 Correct 62 ms 10984 KB Output is correct
21 Correct 63 ms 10996 KB Output is correct
22 Correct 46 ms 10680 KB Output is correct
23 Correct 46 ms 9916 KB Output is correct
24 Correct 55 ms 9788 KB Output is correct
25 Correct 49 ms 10744 KB Output is correct
26 Correct 47 ms 10488 KB Output is correct
27 Correct 54 ms 10724 KB Output is correct
28 Correct 51 ms 10736 KB Output is correct
29 Correct 66 ms 10852 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 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 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 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 1 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 2880 KB Output is correct
15 Correct 30 ms 5392 KB Output is correct
16 Correct 47 ms 8456 KB Output is correct
17 Correct 77 ms 10980 KB Output is correct
18 Correct 62 ms 10916 KB Output is correct
19 Correct 62 ms 10936 KB Output is correct
20 Correct 62 ms 10984 KB Output is correct
21 Correct 63 ms 10996 KB Output is correct
22 Correct 46 ms 10680 KB Output is correct
23 Correct 46 ms 9916 KB Output is correct
24 Correct 55 ms 9788 KB Output is correct
25 Correct 49 ms 10744 KB Output is correct
26 Correct 47 ms 10488 KB Output is correct
27 Correct 54 ms 10724 KB Output is correct
28 Correct 51 ms 10736 KB Output is correct
29 Correct 66 ms 10852 KB Output is correct
30 Correct 163 ms 49124 KB Output is correct
31 Runtime error 227 ms 107980 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -