oj.uz

Submission #72505

# Submission time Handle Problem Language Result Execution time Memory
72505 2018-08-26T08:38:51 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 175 ms 12540 KB 
#include <bits/stdc++.h>

using namespace std;

struct lr{
	int id, l, r;
	lr() {}
	lr(int id, int l, int r) : id(id), l(l), r(r) {}
};

vector <lr> V[101010];
int A[101010], I[101010];
int T[303030], L[303030], R[303030];
int Q[55], dp1[55][22], dp2[55][22];
int n, k, sz;

void query()
{
	int i, j, l, x, y;
	
	if(k == 1){
		printf("%d %d\n", I[Q[1]], I[Q[1]]);
		return;
	}
	
	sort(Q + 1, Q + k + 1, [&](int &ca, int &cb){
		return I[ca] < I[cb];
	});
	
	for(i=1; i<=k; i++){
		for(j=0; j<20; j++) dp1[i][j] = dp2[i][j] = 0;
	}
	
	x = V[Q[1]].size();
	for(j=0; j<x; j++) dp1[1][j] = V[Q[1]][j].l;
	
	for(i=2; i<=k; i++){
		x = V[Q[i]].size();
		for(j=1; j<x; j++){
			for(l=0; l<j; l++){
				if(dp1[i-1][l] && V[Q[i-1]][l].r + 1 == V[Q[i]][j].l){
					dp1[i][j] = dp1[i-1][l];
					break;
				}
			}
		}
	}
	
	x = V[Q[k]].size();
	for(j=0; j<x; j++) dp2[k][j] = V[Q[k]][j].r;
	
	for(i=k-1; i>=1; i--){
		x = V[Q[i]].size();
		for(j=1; j<x; j++){
			for(l=0; l<j; l++){
				if(dp2[i+1][l] && V[Q[i+1]][l].l == V[Q[i]][j].r + 1){
					dp2[i][j] = dp2[i+1][l];
					break;
				}
			}
		}
	}
	
	x = V[Q[1]].size();
	for(j=0; j<x; j++){
		if(dp2[1][j]){
			printf("%d %d\n", V[Q[1]][j].l, dp2[1][j]);
			return;
		}
	}
	
	x = V[Q[k]].size();
	for(j=0; j<x; j++){
		if(dp1[k][j]){
			printf("%d %d\n", dp1[k][j], V[Q[k]][j].r);
			return;
		}
	}
	
	
	for(i=1; i<k; i++){
		x = V[Q[i]].size(); y = V[Q[i+1]].size();
		for(j=0; j<x; j++) for(l=0; l<y; l++){
			if(dp1[i][j] && dp2[i+1][l] && V[Q[i]][j].r + 1 == V[Q[i+1]][l].l){
				if(j == l && V[Q[i+1]][l].id & 1) continue;
				printf("%d %d\n", dp1[i][j], dp2[i+1][l]);
				return;
			}
		}
	}
	
	printf("-1\n");
}

int main()
{
	int q, i;
	
	scanf("%d%d", &n, &q);
	
	for(sz=1; sz<n; sz<<=1);
	
	for(i=0; i<n; i++){
		scanf("%d", A + i);
		I[A[i]] = i + 1;
	}
	
	for(i=0; i<n; i++){
		T[sz + i] = A[i];
		L[sz + i] = i + 1; R[sz + i] = i + 1;
		V[A[i]].emplace_back(sz + i, i + 1, i + 1);
	}
	for(; i<sz; i++){
		T[sz + i] = 1e9;
		L[sz + i] = i + 1; R[sz + i] = i + 1;
	}
	
	for(i=sz-1; i; i--){
		T[i] = min(T[i << 1], T[i << 1 | 1]);
		L[i] = L[i << 1]; R[i] = R[i << 1 | 1];
		if(R[i] <= n) V[T[i]].emplace_back(i, L[i], R[i]);
	}
	
	for(; q--; ){
		scanf("%d", &k);
		for(i=1; i<=k; i++) scanf("%d", Q + i);
		query();
	}
	
	return 0;
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
   ~~~~~^~~~~~~~~~~~~
easy.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
easy.cpp:126:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(i=1; i<=k; i++) scanf("%d", Q + i);
                       ~~~~~^~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct
2 Correct 5 ms 2788 KB Correct
3 Correct 7 ms 2992 KB Correct
4 Correct 14 ms 2992 KB Correct
5 Correct 5 ms 2992 KB Correct
6 Correct 21 ms 3036 KB Correct
7 Correct 15 ms 3084 KB Correct
8 Correct 34 ms 3100 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct
2 Correct 5 ms 2788 KB Correct
3 Correct 7 ms 2992 KB Correct
4 Correct 14 ms 2992 KB Correct
5 Correct 5 ms 2992 KB Correct
6 Correct 21 ms 3036 KB Correct
7 Correct 15 ms 3084 KB Correct
8 Correct 34 ms 3100 KB Correct
9 Correct 88 ms 12200 KB Correct
10 Correct 47 ms 12200 KB Correct
11 Correct 44 ms 12200 KB Correct
12 Correct 134 ms 12200 KB Correct
13 Correct 109 ms 12200 KB Correct
14 Correct 159 ms 12328 KB Correct
15 Correct 175 ms 12472 KB Correct
16 Correct 171 ms 12540 KB Correct
17 Correct 134 ms 12540 KB Correct