Submission #123689

#	Time	Username	Problem	Language	Result	Execution time	Memory
123689		khsoo01	Examination (JOI19_examination)	C++11	100 / 100	1010 ms	57772 KiB

examination

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

const int L = 131072;

int n, q, ans[L];
pair<int,int> a[L];

vector<int> cpr;
vector<pair<int, pair<int,int> > > v;
vector<pair<pair<int,int>, pair<int,int> > > w;

struct seg1D {
	vector<int> v, i;
	void init (int X) {
		i.push_back(X);
		v.assign(2, 0);
	}
	void init (seg1D &A, seg1D &B) {
		for(auto &T : A.i) i.push_back(T);
		for(auto &T : B.i) i.push_back(T);
		sort(i.begin(), i.end());
		v.assign(i.size() * 2, 0);
	}
	void upd (int I, int V) {
		int P = lower_bound(i.begin(), i.end(), I) - i.begin();
		P += i.size();
		while(P) {
			v[P] += V;
			P /= 2;
		}
	}
	int get (int I) {
		int S = lower_bound(i.begin(), i.end(), I) - i.begin();
		int E = (int)i.size() - 1;
		S += i.size(); E += i.size();
		int R = 0;
		while(S <= E) {
			if(S%2 == 1) R += v[S++];
			if(E%2 == 0) R += v[E--];
			S /= 2; E /= 2;
		}
		return R;
	}
};

struct seg2D {
	seg1D v[2*L];
	void init () {
		for(int i=0;i<L;i++) {
			v[L+i].init(i < n ? a[i].Y : 0);
		}
		for(int i=L;--i;) {
			v[i].init(v[2*i], v[2*i+1]);
		}
	}
	void upd (int A, int B, int V) {
		A += L;
		while(A) {
			v[A].upd(B, V);
			A /= 2;
		}
	}
	int get (int A, int B) {
		int S = A + L, E = L-1 + L;
		int R = 0;
		while(S <= E) {
			if(S%2 == 1) R += v[S++].get(B);
			if(E%2 == 0) R += v[E--].get(B);
			S /= 2; E /= 2;
		}
		return R;
	}
} seg;

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++) {
		scanf("%d%d",&a[i].X,&a[i].Y);
	}
	sort(a, a+n);
	for(int i=0;i<n;i++) {
		v.push_back({a[i].X + a[i].Y, {i, a[i].Y}});
		cpr.push_back(a[i].X);
	}
	seg.init();
	for(int i=1;i<=q;i++) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		A = lower_bound(cpr.begin(), cpr.end(), A) - cpr.begin();
		w.push_back({{C, i}, {A, B}});
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	for(int i=w.size(),j=(int)v.size()-1;i--;) {
		while(j >= 0 && v[j].X >= w[i].X.X) {
			seg.upd(v[j].Y.X, v[j].Y.Y, 1);
			j--;
		}
		ans[w[i].X.Y] = seg.get(w[i].Y.X, w[i].Y.Y);
	}
	for(int i=1;i<=q;i++) {
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
examination.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i].X,&a[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&A,&B,&C);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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