oj.uz

Submission #503540

# Submission time Handle Problem Language Result Execution time Memory
503540 2022-01-08T10:28:40 Z mars4 Examination (JOI19_examination) C++17
2 / 100
 3000 ms 17660 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+M-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;
		a2.push_back(q[i].l);
		b2.push_back(q[i].r);
		c2.push_back(q[i].c);
	}
	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+m);
	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 1 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 0 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 94 ms 928 KB Output is correct
8 Correct 97 ms 932 KB Output is correct
9 Correct 99 ms 844 KB Output is correct
10 Correct 88 ms 880 KB Output is correct
11 Correct 93 ms 876 KB Output is correct
12 Correct 86 ms 824 KB Output is correct
13 Correct 88 ms 920 KB Output is correct
14 Correct 85 ms 916 KB Output is correct
15 Correct 85 ms 916 KB Output is correct
16 Correct 96 ms 860 KB Output is correct
17 Correct 99 ms 844 KB Output is correct
18 Correct 53 ms 716 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3009 ms 17660 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 3009 ms 17660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 94 ms 928 KB Output is correct
8 Correct 97 ms 932 KB Output is correct
9 Correct 99 ms 844 KB Output is correct
10 Correct 88 ms 880 KB Output is correct
11 Correct 93 ms 876 KB Output is correct
12 Correct 86 ms 824 KB Output is correct
13 Correct 88 ms 920 KB Output is correct
14 Correct 85 ms 916 KB Output is correct
15 Correct 85 ms 916 KB Output is correct
16 Correct 96 ms 860 KB Output is correct
17 Correct 99 ms 844 KB Output is correct
18 Correct 53 ms 716 KB Output is correct
19 Execution timed out 3009 ms 17660 KB Time limit exceeded
20 Halted 0 ms 0 KB -