Submission #404282

#	Time	Username	Problem	Language	Result	Execution time	Memory
404282		AriaH	Examination (JOI19_examination)	C++11	100 / 100	718 ms	93228 KiB

examination

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 18;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n;

struct segment
{
	int A[N];
	vector < int > seg[N << 2], I[N << 2];
	void Set(int id, int x)
	{
		A[id] = x;
	}
	void Merge(int v)
	{
		int i = 0, j = 0, n1 = SZ(seg[v << 1]), m = SZ(seg[v << 1 | 1]);
		I[v].push_back(0);
		while(i < n1 || j < m)
		{
			if(i < n1 && (j == m || seg[v << 1][i] < seg[v << 1 | 1][j]))
			{
				seg[v].push_back(seg[v << 1][i ++]);
				I[v].push_back(I[v].back() + 1);
			}
			else
			{
				seg[v].push_back(seg[v << 1 | 1][j ++]);
				I[v].push_back(I[v].back());
			}
		}
	}
	void build(int v = 1, int tl = 1, int tr = n)
	{
		if(tl == tr)
		{
			seg[v].push_back(A[tl]);
			return;
		}
		int mid = (tl + tr) >> 1;
		build(v << 1, tl, mid);
		build(v << 1 | 1, mid + 1, tr);
		Merge(v);
	}
	int G(int l, int r, int id, int v = 1, int tl = 1, int tr = n)
	{
		if(l > tr || r < tl || l > r) return 0;
		if(l <= tl && tr <= r)
		{
			return id;
		}
		int mid = (tl + tr) >> 1;
		return G(l, r, I[v][id], v << 1, tl, mid) + G(l, r, id - I[v][id], v << 1 | 1, mid + 1, tr);
	}
	int get(int l, int r, int x) /// tedad adad l, r, ke A[i] < x
	{
		int id = lower_bound(all(seg[1]), x) - seg[1].begin();
		return G(l, r, id);
	}
};

int q, ord[N], S[N], T[N], A[N], B[N], C[N];

bool cmp(int i, int j)
{
	return S[i] + T[i] < S[j] + T[j];
}

int main()
{
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d", &S[i], &T[i]);
		ord[i] = i;
	}
	for(int i = 1; i <= q; i ++)
	{
		scanf("%d%d%d", &A[i], &B[i], &C[i]);
		C[i] = max(C[i], A[i] + B[i]);
	}
	sort(ord + 1, ord + n + 1, cmp);
	segment segS, segT;
	vector < int > vec;
	for(int i = 1; i <= n; i ++)
	{
		///printf("i = %d ord = %d fir = %d sec = %d\n", i, ord[i], S[ord[i]], T[ord[i]]);
		segS.Set(i, S[ord[i]]);
		segT.Set(i, T[ord[i]]);
		vec.push_back(S[ord[i]] + T[ord[i]]);
	}
	segS.build();
	segT.build();
	for(int i = 1; i <= q; i ++)
	{
		int id = lower_bound(all(vec), C[i]) - vec.begin() + 1;
		///printf("i = %d id = %d A : %d B : %d\n", i, id, segS.get(id, n, A[i]), segT.get(id, n, B[i]));
		printf("%d\n", n - id + 1 - segS.get(id, n, A[i]) - segT.get(id, n, B[i]));
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &S[i], &T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d%d%d", &A[i], &B[i], &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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