Submission #1092582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092582		Sunbae	Martian DNA (BOI18_dna)	C++17	100 / 100	108 ms	19536 KiB

dna

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int req[N], a[N], fq[N];
set<int> s;
vector<int> v[N];
signed main(){
	int n, k, m; scanf("%d %d %d", &n, &k, &m);
	for(int i = 0; i<n; ++i) scanf("%d", a+i), v[a[i]].push_back(i);
	for(int i = 0, x; i<m; ++i){ scanf("%d", &x); scanf("%d", req+x); s.insert(x);}
	int l = 0, r = n, mn;
	for(int i = 0; i<n; ++i){
		++fq[a[i]];
		if(fq[a[i]] >= req[a[i]]){
			auto itr = s.find(a[i]);
			if(itr != s.end()) s.erase(itr);
		}
		if(s.empty()){ r = i; mn = r+1; break;}
	}
	if(r >= n){ puts("impossible"); return 0;}
	for(l = 1; l<n; ++l){
		--fq[a[l-1]];
		if(fq[a[l-1]] < req[a[l-1]]){
			int j = upper_bound(v[a[l-1]].begin(), v[a[l-1]].end(), r) - v[a[l-1]].begin();
			if(j >= v[a[l-1]].size()) break;
			int nr = v[a[l-1]][j];
			for(int i = r+1; i <= nr; ++i) ++fq[a[i]];
			r = nr; 
		}
		mn = min(mn, r-l+1);
	}
	printf("%d", mn);
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:25:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    if(j >= v[a[l-1]].size()) break;
      |       ~~^~~~~~~~~~~~~~~~~~~
dna.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  int n, k, m; scanf("%d %d %d", &n, &k, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:9:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for(int i = 0; i<n; ++i) scanf("%d", a+i), v[a[i]].push_back(i);
      |                           ~~~~~^~~~~~~~~~~
dna.cpp:10:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  for(int i = 0, x; i<m; ++i){ scanf("%d", &x); scanf("%d", req+x); s.insert(x);}
      |                               ~~~~~^~~~~~~~~~
dna.cpp:10:53: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  for(int i = 0, x; i<m; ++i){ scanf("%d", &x); scanf("%d", req+x); s.insert(x);}
      |                                                ~~~~~^~~~~~~~~~~~~
dna.cpp:11:20: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   11 |  int l = 0, r = n, mn;
      |                    ^~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32