oj.uz

답안 #554931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554931 2022-04-29T16:04:38 Z new_acc Martian DNA (BOI18_dna) C++14
0 / 100
 97 ms 6040 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],lim[N],il[N],g[N];
ull pot[N];
void solve(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) cin>>t[i];
    pot[0]=1;
    for(int i=1;i<=m;i++) pot[i]=pot[i-1]*p2;
    for(int i=0;i<k;i++) lim[i]=INFi;
    for(int a,b,i=1;i<=m;i++){
        cin>>a>>b;
        lim[a]=b,g[a]=i;
    }
    int res=-1,wsk=1;
    ull curr=0,total=0;
    for(int i=1;i<=m;i++) total+=pot[i];
    for(int i=1;i<=n;i++){
        wsk=max(wsk,i); 
        while(wsk<=n and curr!=total){
            il[t[wsk]]++;
            if(lim[t[wsk]]==il[t[wsk]]) curr+=pot[g[t[wsk]]];
            wsk++;
        }
        if(wsk<=n) res=(res==-1?wsk-i:min(res,wsk-i));
        il[t[i]]--; 
        if(lim[t[i]]==il[t[i]]+1) curr-=pot[g[t[i]]];
    }
    if(res==-1) cout<<"impossible\n";
    else cout<<res<<"\n";
}
int main(){
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 1480 KB Output is correct
2 Correct 29 ms 1492 KB Output is correct
3 Correct 30 ms 1488 KB Output is correct
4 Correct 29 ms 1520 KB Output is correct
5 Correct 54 ms 2876 KB Output is correct
6 Incorrect 31 ms 1504 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 4388 KB Output is correct
2 Correct 77 ms 3780 KB Output is correct
3 Correct 67 ms 3192 KB Output is correct
4 Correct 30 ms 1484 KB Output is correct
5 Correct 96 ms 4948 KB Output is correct
6 Correct 97 ms 6040 KB Output is correct
7 Correct 51 ms 2216 KB Output is correct
8 Correct 55 ms 2528 KB Output is correct
9 Correct 28 ms 1432 KB Output is correct
10 Correct 28 ms 1468 KB Output is correct
11 Correct 29 ms 1444 KB Output is correct
12 Correct 29 ms 1492 KB Output is correct
13 Correct 51 ms 2892 KB Output is correct
14 Incorrect 28 ms 1500 KB Output isn't correct
15 Halted 0 ms 0 KB -