oj.uz

Submission #503541

# Submission time Handle Problem Language Result Execution time Memory
503541 2022-01-08T10:32:27 Z mars4 Examination (JOI19_examination) C++17
2 / 100
 3000 ms 12176 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int64_t
#define ld              long double
#define nl              cout<<"\n"
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class T> ostream& operator<<(ostream& out,ordered_set<T> &s)           {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
	#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
	#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

class Fentree
{
	ll N;
	ll logN;

	ll sum(ll i)
	{
		ll res=0;
		for(;i;i-=i&(-i))
			res+=fentree[i];
		return res;
	}

	public:
	vector<ll> fentree;

	void init(ll n)
	{
		N=n;
		logN=65-__builtin_clzll(n);
		fentree=vector<ll>(N+1);
	}

	void build(vector<ll> &a)
	{
		for(ll i=1;i<=N;i++)
		{
			fentree[i]+=a[i-1];
			if(i+(i&-i)<=N)
				fentree[i+(i&-i)]+=fentree[i];
		}
	}

	void update(ll i,ll val)
	{
		for(i++;i<=N;i+=i&(-i))
			fentree[i]+=val;
	}

	ll sum(ll l,ll r)
	{
		return sum(r+1)-sum(l);
	}

	ll kth_element(ll k)
	{
		ll val=0;
		ll pos=0;
		for(ll i=logN;i>=0;i--)
		{
			ll r=1ll<<i;
			if(pos+r<=N and val+fentree[pos+r]<k)
			{
				val+=fentree[pos+r];
				pos+=r;
			}
		}
		return pos;
	}
};

const ll B=320;

struct query 
{
	ll l,r,c,id;
	bool operator < (const query &o) const 
	{
		if(l/B==o.l/B) 
		{
			if((l/B)%2==0) 
				return r<o.r;
			else 
				return r>o.r;
		} 
		else 
			return l<o.l;
	}
};

vector<pair<ll,ll>> a;
vector<pair<ll,ll>> b;
vector<ll> c;
vector<ll> cnt;
Fentree f;
ll N,M;

class Mo
{
	ll L=-1;
	ll R=-1;

	void updatel(ll i)
	{
		auto [val,id]=a[i];
		cnt[id]++;
		if(cnt[id]==2)
		{
			f.update(c[id],1);
		}
	}

	void removel(ll i)
	{
		auto [val,id]=a[i];
		if(cnt[id]==2)
		{
			f.update(c[id],-1);
		}
		cnt[id]--;
	}

	void updater(ll i)
	{
		auto [val,id]=b[i];
		cnt[id]++;
		if(cnt[id]==2)
		{
			f.update(c[id],1);
		}
	}

	void remover(ll i)
	{
		auto [val,id]=b[i];
		if(cnt[id]==2)
		{
			f.update(c[id],-1);
		}
		cnt[id]--;
	}

	public:
	ll query(query q)
	{
		ll l=q.l;
		ll r=q.r;
		ll c=q.c;
		while(L>=0 and a[L].ff>=l)
		{
			updatel(L);
			L--;
		}
		while(L+1<N and a[L+1].ff<l)
		{
			L++;
			removel(L);
		}
		while(R>=0 and b[R].ff>=r)
		{
			updater(R);
			R--;
		}
		while(R+1<N and b[R+1].ff<r)
		{
			R++;
			remover(R);
		}
		return f.sum(c,N-1);
	}
};

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	cin>>n>>m;
	N=n,M=m;
	a=vector<pair<ll,ll>>(n);
	b=vector<pair<ll,ll>>(n);
	c=vector<ll>(n);
	cnt=vector<ll>(n,2);
	vector<ll> a2;
	vector<ll> b2;
	vector<ll> c2;
	forn(i,0,n)
	{
		cin>>a[i].ff>>b[i].ff;
		a[i].ss=i;
		b[i].ss=i;
		c[i]=a[i].ff+b[i].ff;
		a2.push_back(a[i].ff);
		b2.push_back(b[i].ff);
		c2.push_back(c[i]);
	}
	vector<query> q(m);
	forn(i,0,m)
	{
		cin>>q[i].l>>q[i].r>>q[i].c;
		q[i].id=i;
	}
	sort(all(a2));
	sort(all(b2));
	sort(all(c2));
	for(auto &[l,r]:a)
	{
		l=lower_bound(all(a2),l)-a2.begin();
	}
	for(auto &[l,r]:b)
	{
		l=lower_bound(all(b2),l)-b2.begin();
	}
	for(auto &l:c)
	{
		l=lower_bound(all(c2),l)-c2.begin();
	}
	for(auto &[l,r,c,id]:q)
	{
		l=lower_bound(all(a2),l)-a2.begin();
		r=lower_bound(all(b2),r)-b2.begin();
		c=lower_bound(all(c2),c)-c2.begin();
	}
	f.init(n);
	for(ll i:c)
	{
		f.update(i,1);
	}
	sort(all(a));
	sort(all(b));
	Mo mo;
	vector<ll> ans(m);
	for(auto qu:q)
	{
		ans[qu.id]=mo.query(qu);
	}
	for(ll i:ans)
	{
		cout<<i<<"\n";
	}
	cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:210:5: warning: unused variable 'z' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
examination.cpp:210:11: warning: unused variable 't' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
examination.cpp:210:13: warning: unused variable 'k' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
examination.cpp:210:15: warning: unused variable 'i' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
examination.cpp:210:17: warning: unused variable 'j' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                 ^
examination.cpp:210:19: warning: unused variable 'l' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                   ^
examination.cpp:210:21: warning: unused variable 'd' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                     ^
examination.cpp:210:23: warning: unused variable 'h' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^
examination.cpp:210:25: warning: unused variable 'r' [-Wunused-variable]
  210 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 90 ms 676 KB Output is correct
8 Correct 87 ms 672 KB Output is correct
9 Correct 100 ms 680 KB Output is correct
10 Correct 94 ms 680 KB Output is correct
11 Correct 83 ms 692 KB Output is correct
12 Correct 81 ms 588 KB Output is correct
13 Correct 86 ms 688 KB Output is correct
14 Correct 91 ms 688 KB Output is correct
15 Correct 86 ms 588 KB Output is correct
16 Correct 87 ms 588 KB Output is correct
17 Correct 87 ms 684 KB Output is correct
18 Correct 55 ms 676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3094 ms 12176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3094 ms 12176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 90 ms 676 KB Output is correct
8 Correct 87 ms 672 KB Output is correct
9 Correct 100 ms 680 KB Output is correct
10 Correct 94 ms 680 KB Output is correct
11 Correct 83 ms 692 KB Output is correct
12 Correct 81 ms 588 KB Output is correct
13 Correct 86 ms 688 KB Output is correct
14 Correct 91 ms 688 KB Output is correct
15 Correct 86 ms 588 KB Output is correct
16 Correct 87 ms 588 KB Output is correct
17 Correct 87 ms 684 KB Output is correct
18 Correct 55 ms 676 KB Output is correct
19 Execution timed out 3094 ms 12176 KB Time limit exceeded
20 Halted 0 ms 0 KB -