oj.uz

Submission #209063

# Submission time Handle Problem Language Result Execution time Memory
209063 2020-03-13T05:45:03 Z YJU Examination (JOI19_examination) C++14
0 / 100
 618 ms 21040 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,pll> tyty;
const ll N=1e6+5;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define lwb lower_bound
#define Y second
#define SZ(a) (ll)a.size()

ll bit[N],n,q,s,t,a,b,c,ans[N];
vector<tyty> v;
vector<ll> lis;

void add(ll id,ll d){
	while(id<N)bit[id]+=d,id+=(id&-id);
}

ll Q(ll id){
	ll tmp=0;
	while(id)tmp+=bit[id],id-=(id&-id);
	return tmp;
}

void CDQ(ll l,ll r){
	cout<<l<<" "<<r<<"\n";
	if(r==l+1)return;
	ll mid=(l+r)/2;
	CDQ(l,mid);CDQ(mid,r);
	ll ql=l,qr=mid;
	vector<ll> que;
	while(ql<mid&&qr<r){
		if(v[ql].X.Y<=v[qr].X.Y){
			if(v[ql].Y.Y==0)add(v[ql].Y.X,1),que.pb(v[ql].Y.X);
			++ql;
		}else{
			if(v[qr].Y.Y!=0)ans[v[qr].Y.Y]+=Q(v[qr].Y.X);
			++qr;
		}
	}
	//while(ql<mid)
	while(qr<r)if(v[qr].Y.Y!=0)ans[v[qr].Y.Y]+=Q(v[qr].Y.X),++qr;else ++qr;
	for(ll i:que){add(i,-1);}
	sort(v.begin()+l,v.begin()+r,[](tyty a,tyty b){return (a.X.Y!=b.X.Y?a.X.Y<b.X.Y:a.Y.Y<b.Y.Y);});
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	REP(i,n)cin>>s>>t,v.pb(mp(mp(-s,-t),mp(-(s+t),0))),lis.pb(-s),lis.pb(-t),lis.pb(-s-t);
	REP1(i,q)cin>>a>>b>>c,v.pb(mp(mp(-a,-b),mp(-c,i))),lis.pb(-a),lis.pb(-b),lis.pb(-c);
	sort(lis.begin(),lis.end());
	lis.resize(unique(lis.begin(),lis.end())-lis.begin());
	for(auto &i:v){
		i.X.X=lwb(lis.begin(),lis.end(),i.X.X)-lis.begin()+1;
		i.X.Y=lwb(lis.begin(),lis.end(),i.X.Y)-lis.begin()+1;
		i.Y.X=lwb(lis.begin(),lis.end(),i.Y.X)-lis.begin()+1;
	}
	sort(v.begin(),v.end());
	CDQ(0,SZ(v));
	REP1(i,q)cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 21040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 21040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -