oj.uz

Submission #651150

# Submission time Handle Problem Language Result Execution time Memory
651150 2022-10-17T12:47:06 Z jcelin Martian DNA (BOI18_dna) C++14
0 / 100
 116 ms 13832 KB 
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

vi ind[MAXN];
int req[MAXN];
int arr[MAXN];
set<int> cur;

//prvi
int point[MAXN];

void solve(){
	int n, r, k;
	cin >> n >> k >> r;
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		arr[i] = x; 
		ind[x].PB(i);
	}
	
	for(int i=0; i<r; i++){
		int a, b;
		cin >> a >> b;
		req[a] = b;
	}
	
	
	
	for(int i=0; i<k; i++){
		if(req[i] > ind[i].size()){
			cout << "impossible\n";
			return;
		}
		
		for(int j=0; j<req[i]; j++) cur.insert(ind[i][j]);
		point[i] = req[i] - 1;
	}
	
	int ans = *(--cur.end()) - *cur.begin();
	
	
	for(int i=1; i<n; i++){
		int pre = arr[i - 1];
		if(req[pre] == 0) continue;
		
		cur.erase(i - 1);
		if(point[pre] >= ind[pre].size()) break;
		point[pre]++;
		cur.insert(ind[pre][point[pre]]);
		ans = min(ans, *(--cur.end()) - *cur.begin());
	}
	
	cout << ans + 1 << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Compilation message

dna.cpp: In function 'void solve()':
dna.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   if(req[i] > ind[i].size()){
      |      ~~~~~~~^~~~~~~~~~~~~~~
dna.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   if(point[pre] >= ind[pre].size()) break;
      |      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 5036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Incorrect 4 ms 5076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 11332 KB Output is correct
2 Correct 51 ms 8820 KB Output is correct
3 Correct 32 ms 7124 KB Output is correct
4 Correct 41 ms 9988 KB Output is correct
5 Incorrect 32 ms 9872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 13832 KB Output is correct
2 Correct 93 ms 12552 KB Output is correct
3 Incorrect 52 ms 10444 KB Output isn't correct
4 Halted 0 ms 0 KB -