Submission #997977

#	Time	Username	Problem	Language	Result	Execution time	Memory
997977		vjudge1	Examination (JOI19_examination)	C++17	0 / 100	3057 ms	16576 KiB

examination

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#pragma GCC target("avx,avx2,fma")
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define lowbit(x) x&-x
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ff(x,a,b,c) for (auto x=a;x<=b;x+=c)
#define fd(x,a,b,c) for (auto x=a;x>=b;x-=c)
#define int ll

using namespace std;

const int N = 2e5+5;
const int mod = 1e9+7;
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

map<int,int> cnt;
vector<array<int,4>> s;
int n,q;
int ans[N]; 

bool cmp(array<int,4> a,array<int,4> b)
{
	return a[0]>b[0] || (a[0]==b[0] && a[3]<b[3]);
}

struct bintree{
	vector<int> st;
	vector<int> lazy;
	void init()
	{
		st.resize(200005,0); lazy.resize(200005,0);
	}
	void update(int id,int val)
	{
		while (id<=cnt.size())
		{
			if (lazy[id]!=val) lazy[id] = val,st[id] = 0;
		}
		st[id]++;
		id += lowbit(id);
	} 
	int sum (int id,int x)
	{
		int ans = 0;
		while (id>0)
		{
			if (lazy[id]!=x) lazy[id] = x,st[id] = 0;
			ans+=st[id];
			id-=lowbit(id);
		}
		return ans;
	}
} bit;

void cdq(int id,int l,int r)
{
	if (l==r) return;
	int mid = l+(r-l)/2;
	cdq(id*2,l,mid); cdq(id*2+1,mid+1,r);
	int i = l,j = mid+1;
	vector<array<int,4>> a;
	while (i<=mid && j<=r)
	{
		if (s[i][1]>=s[j][1])
		{
			if (s[i][3]==-1) bit.update(cnt.size(),id);
			a.pb(s[i]); i++;
		} else 
		{
			if (s[j][3]!=-1) ans[s[j][3]]+=bit.sum(cnt.size()-s[j][2],id);
			a.pb(s[j]); j++;
		}
	}
	while (i<=mid) a.pb(s[i]),i++;
	while (j<=r)
	{
		if (s[j][3]!=-1) ans[s[j][3]]+=bit.sum(cnt.size()-s[j][2],id);
		a.pb(s[j]); j++;
	}
	for (int i=l;i<=r;i++) swap(s[i],a[i-l]);
}

void solve()
{
	bit.init();
	cin>>n>>q;
	for (int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y;
		s.pb({x,y,x+y,-1});
		cnt[x+y] = 1;
	}
	for (int i=0;i<q;i++)
	{
		int x,y,z; cin>>x>>y>>z;
		s.pb({x,y,z,i});
		cnt[z]++;
	}
	sort(s.begin(),s.end(),cmp);
	int idx = 0;
	for (auto &[a,b] : cnt) b = idx++;
	for (auto &[a,b,c,d] : s) c = cnt[c];
	cdq(1,0,cnt.size()-1);
	for (int i=0;i<q;i++) cout<<ans[i];
}

signed main()
{
	bruh
	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

Compilation message (stderr)

examination.cpp: In member function 'void bintree::update(long long int, long long int)':
examination.cpp:41:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   while (id<=cnt.size())
      |          ~~^~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57