Submission #839497

#	Time	Username	Problem	Language	Result	Execution time	Memory
839497		Thanhs	Examination (JOI19_examination)	C++14	100 / 100	741 ms	60952 KiB

examination

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef stack<int> si;
typedef queue<int> qi;
typedef deque<int> di;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define fi first
#define se second
#define gcd __gcd
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))

const int MAXN=1e5+5;
const long long inf=1e18;
const int MOD=1e9+7;

struct query
{
	int x,y,z,idx;
	query(const int& x,const int& y,const int& z,const int& idx):x(x),y(y),z(z),idx(idx){}
	bool operator <(const query& other) {return z>other.z;}
};

struct stud
{
	int s,t;
	stud(const int& s,const int& t):s(s),t(t){}
	bool operator <(const stud& other) {return s+t>other.s+other.t;}
};

vector<query> q;
vector<stud> st;
int n,m,ans[MAXN];
vector<int> xs,ys;
vector<vector<int>> node,bit;

void fakeupd(int x,int y)
{
	for(;x<=xs.size();x+=x&-x) node[x].pb(y);
}

void fakeget(int x,int y)
{
	for(;x>0;x-=x&-x) node[x].pb(y);
}

void upd(int x,int yy)
{
	for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
}

int get(int x,int yy)
{
	int res=0;
	for(;x>0;x-=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y>0;y-=y&-y) res+=bit[x][y-1];
	return res;
}

int xid(const int& x)
{
	return lower_bound(xs.begin(),xs.end(),x,greater<int>())-xs.begin();
}

int yid(const int& y)
{
	return lower_bound(ys.begin(),ys.end(),y,greater<int>())-ys.begin();
}

signed main()
{
	fastIO
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	cin>>n>>m;
	FOR(i,0,n-1) {int s,t; cin>>s>>t; st.emplace_back(s,t); xs.pb(s); ys.pb(t);}
	FOR(i,0,m-1) {int x,y,z; cin>>x>>y>>z; q.emplace_back(x,y,z,i); xs.pb(x); ys.pb(y);}
	sort(xs.begin(),xs.end(),greater<int>());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	sort(ys.begin(),ys.end(),greater<int>());
	ys.erase(unique(ys.begin(),ys.end()),ys.end());
	node.resize(xs.size()+1);
	bit.resize(xs.size()+1);
	FOR(i,0,n-1) fakeupd(xid(st[i].s)+1,yid(st[i].t));
	FOR(i,0,m-1) fakeget(xid(q[i].x)+1,yid(q[i].y));
	FOR(i,1,xs.size())
	{
		sort(node[i].begin(),node[i].end());
		node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
		bit[i].resize(node[i].size());
	}
	sort(st.begin(),st.end()); sort(q.begin(),q.end());
	int cur=0;
	FOR(i,0,m-1)
	{
		while(cur<n&&st[cur].s+st[cur].t>=q[i].z) {upd(xid(st[cur].s)+1,yid(st[cur].t)); cur++;}
		ans[q[i].idx]=get(xid(q[i].x)+1,yid(q[i].y));
	}
	FOR(i,0,m-1) cout<<ans[i]<<endl;
}

Compilation message (stderr)

examination.cpp: In function 'void fakeupd(long long int, long long int)':
examination.cpp:53:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(;x<=xs.size();x+=x&-x) node[x].pb(y);
      |       ~^~~~~~~~~~~
examination.cpp: In function 'void upd(long long int, long long int)':
examination.cpp:63:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
      |       ~^~~~~~~~~~~
examination.cpp:63:104: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
      |                                                                                                       ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:18:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define FOR(i,a,b) for(int i = a; i <= b; i++)
......
   99 |  FOR(i,1,xs.size())
      |      ~~~~~~~~~~~~~                   
examination.cpp:99:2: note: in expansion of macro 'FOR'
   99 |  FOR(i,1,xs.size())
      |  ^~~

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