Submission #927286

#TimeUsernameProblemLanguageResultExecution timeMemory
927286vjudge1 Martian DNA (BOI18_dna)C++17
100 / 100
44 ms14432 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC target("popcnt") using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back #define emb emplace_back #define emc emplace #define pii pair<int,int> #define pll pair<ll,ll> #define F first #define S second template <class type_key, class type_val> using um = unordered_map<type_key, type_val>; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, R; cin >> n >> k >> R; int a[n+1]; vector<vector<int>> pos(k+1); vector<int> need(k+1, 0); vector<int> rt(k+1, 0); vector<int> lt(k+1, 0); for( int i = 1; i <= n; i++ ) { cin >> a[i]; pos[a[i]].pb(i); } pii Q[R+1]; int r = 0; for( int i = 1; i <= R; i++ ) { cin >> Q[i].F >> Q[i].S; if( pos[Q[i].F].size() < Q[i].S ) { cout << "impossible"; return 0; } r = max(r, pos[Q[i].F][Q[i].S-1]); need[Q[i].F] = Q[i].S; lt[Q[i].F] = 0; } for( int i = 1; i <= R; i++ ) { rt[Q[i].F] = Q[i].S-1; } int mn = r; for( int l = 1; l <= n; l++ ) { if( need[a[l]] ) { lt[a[l]]++; rt[a[l]]++; if( rt[a[l]] >= pos[a[l]].size() ) break; r = max(r, pos[a[l]][rt[a[l]]]); } mn = min(mn, r-l); } cout << mn; return 0; }

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:46:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |             if( pos[Q[i].F].size() < Q[i].S ) {
      |                                    ^
dna.cpp:63:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                   if( rt[a[l]] >= pos[a[l]].size() ) break;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...