Submission #731705

#	Time	Username	Problem	Language	Result	Execution time	Memory
731705		shadow_sami	Martian DNA (BOI18_dna)	C++17	68 / 100	2062 ms	144484 KiB

dna

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define fip(a,b) for(ll i = a; i < b ; i++)
#define fjp(a,b) for(ll j = a; j < b ; j++)
#define fp(k,a,b) for(ll k = a; k < b ; k++)
#define fin(a,b) for(ll i = a; i >= b ; i--)
#define fjn(a,b) for(ll i = a; j >= b ; j--)
#define fn(k,a,b) for(ll k = a; k >= b ; k--)
#define fx(a) for(auto x : a)
#define ordered_set tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>
#define total_one(k) __builtin_popcount(k)
#define back_zero(k) __builtin_ctzll(k)
#define front_zero(k) __builtin_clzll(k)
#define nli "\n"

ll n,m,ans,sum,res,cnt,tptp,tp,tp2,q;

const ll mx = 2e5 + 5;
const ll mod = 1e9 + 7;

bool f = false;

ll a[mx];
ll tnc[mx];
vi ind[mx];
deque<ll> dq[mx];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// #ifdef code
	// 	freopen("input1.txt","r",stdin);
	// 	freopen("output1.txt","w",stdout);
	// 	freopen("error1.txt","w",stderr);
	// #endif

		cin>>n>>m>>q;
		fip(1,n+1){
			cin>>a[i],tnc[i] = -1;
		}
		vi v;
		fip(0,q){
			cin>>tp>>tp2;
			tnc[tp] = tp2;
			v.push_back(tp);
		}
		ans = 1e9;
		fip(1,n+1){
			if(tnc[a[i]]!=-1){
				dq[a[i]].push_back(i);
				if(dq[a[i]].size()>tnc[a[i]])
					dq[a[i]].pop_front();
			}		
			f = 0;
			fx(v){
				if(tnc[x] != dq[x].size())
					f = 1;
			}
			if(f)
				continue;
			tp = 1e18;
			fx(v){
				tp = min(tp,dq[x].front());
			}
			ans = min(ans,i-tp+1);
		}
		if(ans==1e9){
			cout<<"impossible";
			return 0;
		}
		cout<<ans<<nli;

	// cerr << "Time elapsed : " << setprecision(6) << 100.00 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:59:23: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   59 |     if(dq[a[i]].size()>tnc[a[i]])
      |        ~~~~~~~~~~~~~~~^~~~~~~~~~
dna.cpp:64:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(tnc[x] != dq[x].size())
      |        ~~~~~~~^~~~~~~~~~~~~~~

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