oj.uz

Submission #123684

# Submission time Handle Problem Language Result Execution time Memory
123684 2019-07-02T03:57:59 Z 이온조(#3029) Examination (JOI19_examination) C++14
20 / 100
 242 ms 10896 KB 
#include <bits/stdc++.h>
using namespace std;

const int MXN = 200000;
struct query { int X, Y, Z, id; };
int S[100009], T[100009], ans[100009], F1[200009], F2[200009], F3[200009];

int getx(vector<int> &S, int x) { return lower_bound(S.begin(), S.end(), x) - S.begin() + 1; }

void upd(int F[], int x, int y) { for(int i=x; i<=MXN; i+=(i&-i)) F[i] += y; }
int get(int F[], int x) { int ret = 0; for(int i=x; i>=1; i-=(i&-i)) ret += F[i]; return ret; }

int main() {
	vector<int> XS, YS;
	vector<query> A, B;
	int N, Q; scanf("%d%d",&N,&Q);
	for(int i=1; i<=N; i++) {
		scanf("%d%d", &S[i], &T[i]);
		A.push_back({S[i], T[i], -1, -1});
		B.push_back({S[i], T[i], -1, -1});
		XS.push_back(S[i]);
		YS.push_back(T[i]);
	}
	
	for(int i=0; i<Q; i++) {
		int X, Y, Z; scanf("%d%d%d",&X,&Y,&Z);
		if(X+Y >= Z) A.push_back({X, Y, Z, i});
		else B.push_back({X, Y, Z, i});
		XS.push_back(X);
		YS.push_back(Y);
	}

	sort(XS.begin(), XS.end()); XS.resize(unique(XS.begin(), XS.end()) - XS.begin());
	sort(YS.begin(), YS.end()); YS.resize(unique(YS.begin(), YS.end()) - YS.begin());

	sort(A.begin(), A.end(), [&](query PP, query QQ) {
		if(PP.X == QQ.X) return PP.id < QQ.id;
		return PP.X > QQ.X;
	});
	for(auto& it: A) {
		if(it.id == -1) upd(F1, getx(YS, it.Y), +1);
		else ans[it.id] = get(F1, MXN) - get(F1, getx(YS, it.Y) - 1);
	}
	sort(B.begin(), B.end(), [&](query PP, query QQ) {
		int PZ, QZ;
		if(PP.id == -1) PZ = PP.X + PP.Y;
		else PZ = PP.Z;
		if(QQ.id == -1) QZ = QQ.X + QQ.Y;
		else QZ = QQ.Z;
		if(PZ == QZ) return PP.id < QQ.id;
		return PZ > QZ;
	});
	int cnt = 0;
	for(auto& it: B) {
		if(it.id == -1) {
			upd(F2, getx(XS, it.X), +1);
			upd(F3, getx(YS, it.Y), +1);
			++cnt;
		}
		else ans[it.id] = cnt - get(F2, getx(XS, it.X)) - get(F3, getx(YS, it.Y));
	}
	for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:16:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, Q; scanf("%d%d",&N,&Q);
            ~~~~~^~~~~~~~~~~~~~
examination.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &S[i], &T[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:26:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int X, Y, Z; scanf("%d%d%d",&X,&Y,&Z);
                ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 8 ms 888 KB Output is correct
8 Correct 8 ms 888 KB Output is correct
9 Correct 8 ms 888 KB Output is correct
10 Incorrect 7 ms 888 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10816 KB Output is correct
2 Correct 223 ms 10804 KB Output is correct
3 Correct 223 ms 10704 KB Output is correct
4 Correct 153 ms 10164 KB Output is correct
5 Correct 174 ms 10420 KB Output is correct
6 Correct 123 ms 9780 KB Output is correct
7 Correct 222 ms 10896 KB Output is correct
8 Correct 217 ms 10720 KB Output is correct
9 Correct 208 ms 10640 KB Output is correct
10 Correct 158 ms 10288 KB Output is correct
11 Correct 145 ms 10008 KB Output is correct
12 Correct 99 ms 9400 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10816 KB Output is correct
2 Correct 223 ms 10804 KB Output is correct
3 Correct 223 ms 10704 KB Output is correct
4 Correct 153 ms 10164 KB Output is correct
5 Correct 174 ms 10420 KB Output is correct
6 Correct 123 ms 9780 KB Output is correct
7 Correct 222 ms 10896 KB Output is correct
8 Correct 217 ms 10720 KB Output is correct
9 Correct 208 ms 10640 KB Output is correct
10 Correct 158 ms 10288 KB Output is correct
11 Correct 145 ms 10008 KB Output is correct
12 Correct 99 ms 9400 KB Output is correct
13 Incorrect 242 ms 10704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 8 ms 888 KB Output is correct
8 Correct 8 ms 888 KB Output is correct
9 Correct 8 ms 888 KB Output is correct
10 Incorrect 7 ms 888 KB Output isn't correct
11 Halted 0 ms 0 KB -