#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];
ll mn[mx];
deque<ll> dq[mx];
typedef struct Segment_tree{
vi arr;
ll range;
void init(ll k){
range = log2(k);
range = 1 << (range+3);
arr.resize(range,-100);
return;
}
ll construct(ll ptr,ll l,ll r){
if(l==r){
arr[ptr] = mn[l];
return arr[ptr];
}
ll mid = l + (r-l)/2;
arr[ptr] = min(construct(2*ptr,l,mid),construct(2*ptr+1,mid+1,r));
return arr[ptr];
}
ll query(ll ptr,ll l,ll r,ll st,ll en){
if(l>en || r<st)
return 1e18;
if(l>=st && r<=en)
return arr[ptr];
ll mid = l + (r-l)/2;
return min(query(2*ptr,l,mid,st,en),query(2*ptr+1,mid+1,r,st,en));
}
ll update(ll ptr,ll l,ll r,ll pos,ll val){
if(l==r && r==pos){
mn[r] = val;
arr[ptr] = val;
return arr[ptr] = val;
}
if(l>pos || r<pos)
return arr[ptr];
ll mid = l + (r-l)/2;
arr[ptr] = min(update(2*ptr,l,mid,pos,val),update(2*ptr+1,mid+1,r,pos,val));
return arr[ptr];
}
}SGT;
SGT sgt;
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;
sgt.init(m);
fip(1,n+1){
mn[i] = 1e18;
cin>>a[i],tnc[i] = -1;
}
set<ll> st;
fip(0,q){
cin>>tp>>tp2;
tnc[tp] = tp2;
mn[tp] = -100;
// st.insert(tp);
}
ans = 1e9;
sgt.construct(1,0,m-1);
fip(1,n+1){
if(tnc[a[i]]!=-1){
dq[a[i]].push_back(i);
if((long long)dq[a[i]].size()>tnc[a[i]])
dq[a[i]].pop_front();
if((long long)dq[a[i]].size()==tnc[a[i]])
sgt.update(1,0,m-1,a[i],dq[a[i]].front());
}
tp = sgt.query(1,0,m-1,0,m-1);
if(tp==-100)
continue;
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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
134860 KB |
Output is correct |
| 2 |
Incorrect |
87 ms |
134968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
134980 KB |
Output is correct |
| 2 |
Correct |
93 ms |
135036 KB |
Output is correct |
| 3 |
Incorrect |
85 ms |
135084 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
140768 KB |
Output is correct |
| 2 |
Correct |
111 ms |
140364 KB |
Output is correct |
| 3 |
Correct |
107 ms |
140012 KB |
Output is correct |
| 4 |
Correct |
113 ms |
140488 KB |
Output is correct |
| 5 |
Incorrect |
117 ms |
144828 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
145476 KB |
Output is correct |
| 2 |
Correct |
183 ms |
143220 KB |
Output is correct |
| 3 |
Incorrect |
142 ms |
142896 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
