oj.uz

Submission #458060

# Submission time Handle Problem Language Result Execution time Memory
458060 2021-08-07T23:56:42 Z ZaZo_ Martian DNA (BOI18_dna) C++14
0 / 100
 673 ms 19524 KB 
//Sorry but iam targeting IOI :))
//NEVER LOSE HOPE
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define endl "\n"
#define ceil(a,b)   (a+(b-1))/b
#define all(v) v.begin(),v.end()
#define int long long int
#define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e4+10,mod = 1e9+7;
int32_t main(){
  int n,k,rr;
  cin>>n>>k>>rr;
  int arr[n];
  map<int,int>mp,req,dif;
  set<int>st;
  for(int i = 0 ; i < n ; i ++)
  {
    cin>>arr[i];
  }
  int flg=0;
  for(int i = 0 ; i < rr ; i ++)
  {
    int x,y;
    cin>>x>>y;
    req[x]=y;
  }
  int l=0,r=0,ans=INT_MAX,cnt=0;
  while(l<=r)
  {
    while(r<n && (r<k || cnt<req.size()) )
    {
      mp[arr[r]]++;
      if(req.count(arr[r]) && mp[arr[r]]==req[arr[r]]) cnt++;
      r++;
    }
    if(cnt==req.size())  ans=min(ans,r-l);
    mp[arr[l]]--;
    if(req.count(arr[l])&&req[arr[l]]>mp[arr[l]]) cnt--;
    l++;
  }
  if(ans==INT_MAX)
  {
    cout<<"impossible"<<endl;
    return 0;
  }
  cout<<ans<<endl;
}

Compilation message

dna.cpp: In function 'int32_t main()':
dna.cpp:33:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while(r<n && (r<k || cnt<req.size()) )
      |                          ~~~^~~~~~~~~~~
dna.cpp:39:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(cnt==req.size())  ans=min(ans,r-l);
      |        ~~~^~~~~~~~~~~~
dna.cpp:23:7: warning: unused variable 'flg' [-Wunused-variable]
   23 |   int flg=0;
      |       ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Incorrect 0 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Incorrect 3 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1740 KB Output is correct
2 Correct 41 ms 1740 KB Output is correct
3 Correct 50 ms 1740 KB Output is correct
4 Correct 45 ms 1840 KB Output is correct
5 Correct 204 ms 6828 KB Output is correct
6 Correct 51 ms 1828 KB Output is correct
7 Correct 61 ms 1840 KB Output is correct
8 Incorrect 291 ms 14260 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 11848 KB Output is correct
2 Correct 410 ms 9372 KB Output is correct
3 Correct 252 ms 6844 KB Output is correct
4 Correct 41 ms 1828 KB Output is correct
5 Correct 576 ms 13104 KB Output is correct
6 Correct 673 ms 19524 KB Output is correct
7 Correct 248 ms 2724 KB Output is correct
8 Correct 280 ms 4060 KB Output is correct
9 Correct 46 ms 1740 KB Output is correct
10 Correct 42 ms 1844 KB Output is correct
11 Correct 55 ms 1844 KB Output is correct
12 Correct 46 ms 1828 KB Output is correct
13 Correct 165 ms 6840 KB Output is correct
14 Correct 54 ms 1740 KB Output is correct
15 Correct 63 ms 1740 KB Output is correct
16 Incorrect 268 ms 14372 KB Output isn't correct
17 Halted 0 ms 0 KB -