Submission #493990

#	Time	Username	Problem	Language	Result	Execution time	Memory
493990		patrikpavic2	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	498 ms	47468 KiB

matryoshka

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 4e5 + 500;

int n, q, A[N], B[N], ans[N], C[N], D[N];
vector < int > szA, szB;
vector < int > dod[N], pit[N];

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++){
		scanf("%d%d", A + i, B + i);
		szA.PB(A[i]), szB.PB(B[i]);
	}
	for(int i = 0;i < q;i++){
		scanf("%d%d", C + i, D + i);
		szA.PB(C[i]), szB.PB(D[i]);
	}
	sort(szA.begin(), szA.end()); 
	szA.erase(unique(szA.begin(), szA.end()), szA.end());
	sort(szB.begin(), szB.end());
	szB.erase(unique(szB.begin(), szB.end()), szB.end());
	for(int i = 0;i < n;i++){
		A[i] = lower_bound(szA.begin(), szA.end(), A[i]) - szA.begin();
		B[i] = lower_bound(szB.begin(), szB.end(), B[i]) - szB.begin();
		dod[A[i]].PB(B[i]);	
	}
	for(int i = 0;i < q;i++){
		C[i] = lower_bound(szA.begin(), szA.end(), C[i]) - szA.begin();
		D[i] = lower_bound(szB.begin(), szB.end(), D[i]) - szB.begin();
		pit[C[i]].PB(i);
	}
	vector < int > odg;
	for(int i = N - 1;i >= 0;i--){
		sort(dod[i].begin(), dod[i].end());
		for(int x : dod[i]){
			if((int)odg.size() == 0 || odg.back() <= x)
				odg.PB(x);
			else
				odg[upper_bound(odg.begin(), odg.end(), x) - odg.begin()] = x;
		}
		for(int x : pit[i]){
			ans[x] = upper_bound(odg.begin(), odg.end(), D[x]) - odg.begin();
		}
	}
	for(int i = 0;i < q;i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d%d", C + i, D + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49