| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298568 | HuyAT | Love Polygon (BOI18_polygon) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct Solver{
int n,k,r;
std::vector<int> a,b;
std::vector<std::vector<int>> pos,add,remov;
void readData(){
std::cin >> n >> k >> r;
a.assign(n + 1,0);
b.assign(n + 1,0);
pos.resize(n + 1);
remov.resize(n + 1);
add.resize(n + 1);
for(int i = 1;i <= n;++i){
std::cin >> a[i];
pos[a[i]].emplace_back(i);
}
for(int i = 1;i <= r;++i){
int p;
std::cin >> p;
std::cin >> b[p];
}
}
void solve(){
for(int i = 0;i < k;++i){
if(b[i] == 0){
continue;
}
for(int j = b[i] - 1;j < (int)pos[i].size();++j){
add[pos[i][j]].emplace_back(pos[i][j - b[i] + 1]);
if(j < (int)pos[i].size() - 1){
remov[pos[i][j + 1]].emplace_back(pos[i][j - b[i] + 1]);
}
}
}
std::multiset<int> s;
int ans = V;
for(int i = 1;i <= n;++i){
for(int pos : add[i]){
s.insert(pos);
}
for(int pos : remov[i]){
s.erase(s.find(pos));
}
if((int)s.size() == r){
ans = std::min(ans,i - *s.begin() + 1);
}
}
std::cout << (ans == V ? "impossible" : ans);
}
void main(){
readData();
solve();
}
};
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
Solver().main();
return 0;
}