oj.uz

Submission #404280

# Submission time Handle Problem Language Result Execution time Memory
404280 2021-05-14T04:57:11 Z AriaH Examination (JOI19_examination) C++11
2 / 100
 13 ms 5552 KB 
/** 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 = 1e4 + 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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4044 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 4 ms 4136 KB Output is correct
7 Correct 12 ms 5536 KB Output is correct
8 Correct 12 ms 5552 KB Output is correct
9 Correct 12 ms 5452 KB Output is correct
10 Correct 11 ms 5452 KB Output is correct
11 Correct 11 ms 5452 KB Output is correct
12 Correct 12 ms 5384 KB Output is correct
13 Correct 12 ms 5424 KB Output is correct
14 Correct 12 ms 5536 KB Output is correct
15 Correct 12 ms 5540 KB Output is correct
16 Correct 13 ms 5452 KB Output is correct
17 Correct 11 ms 5516 KB Output is correct
18 Correct 10 ms 5432 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4044 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 4 ms 4136 KB Output is correct
7 Correct 12 ms 5536 KB Output is correct
8 Correct 12 ms 5552 KB Output is correct
9 Correct 12 ms 5452 KB Output is correct
10 Correct 11 ms 5452 KB Output is correct
11 Correct 11 ms 5452 KB Output is correct
12 Correct 12 ms 5384 KB Output is correct
13 Correct 12 ms 5424 KB Output is correct
14 Correct 12 ms 5536 KB Output is correct
15 Correct 12 ms 5540 KB Output is correct
16 Correct 13 ms 5452 KB Output is correct
17 Correct 11 ms 5516 KB Output is correct
18 Correct 10 ms 5432 KB Output is correct
19 Incorrect 11 ms 5072 KB Output isn't correct
20 Halted 0 ms 0 KB -