제출 #1290921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290921		al_reem_2010	Martian DNA (BOI18_dna)	C++20	100 / 100	41 ms	4724 KiB

dna

// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <thread>
#include <fstream>
#include <stack>
using namespace std ;
#define int long long
#define pb push_back
#define si size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
const int inf=1e18 ;
const int mod=1e9+7 ;
const int maxn=2*1e5+7 ;
int tt=1 ;
int a[maxn] , cnt[maxn] , cnt1[maxn] ;
void solve()
{
    int n , r , k ;
    cin >> n >> r >> k ;
    for(int i=0 ; i<n ; i++) {cin >> a[i] ;}
    int x , cntt , c=0 ;
    for(int i=0 ; i<k ; i++) {cin >> x >> cntt ; cnt[x]=cntt ; c+=cnt[x] ;}
    int s=c , e=n , mid , ans=-1 ;
    while(s<=e)
    {
        mid=(s+e)/2 ;
        bool A=0 ;
        for(int i=0 ; i<mid ; i++) {cnt1[a[i]]+=1 ;}
        int B=0 ;
        for(int i=0 ; i<r ; i++) {B+=(cnt[i]<=cnt1[i] ? 1 : 0) ;}
        A=(A|(B==r)) ;
        //cout << 0 << " " << mid-1 << " " << (A ? 1 : 0) << "\n" ;
        for(int i=0 ; mid+i<n ; i++)
        {
            if(cnt[a[i]]<=cnt1[a[i]] && cnt[a[i]]>cnt1[a[i]]-1) {B-=1 ;}
            cnt1[a[i]]-=1 ;
            if(cnt[a[mid+i]]>cnt1[a[mid+i]] && cnt[a[mid+i]]<=cnt1[a[mid+i]]+1) {B+=1 ;}
            cnt1[a[mid+i]]+=1 ;
            A=(A|(B==r)) ;
            //cout << i << " " << mid+i << " " << (A ? 1 : 0) << "\n" ;
        }
        if(A) {ans=mid ; e=mid-1 ;}
        else {s=mid+1 ;}
        for(int i=0 ; i<r ; i++) {cnt1[i]=0 ;}
    }
    if(ans==-1) {cout << "impossible" ; return ;}
    cout << ans ;
}
signed main()
{
    //wrong
    applejuice ;
    //cin >> tt ;
    while(tt--) {solve() ;}
}
/*
 5 2 2
 0 1 1 0 1
 0 1
 1 1
 
 2
 _______
 13 4 3
 1 1 3 2 0 1 2 0 0 0 0 3 1
 0 2
 2 1
 1 2
 
 7
 _______
 5 3 1
 1 2 0 1 2
 0 2
 
 impossible
 */

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