oj.uz

Submission #731705

# Submission time Handle Problem Language Result Execution time Memory
731705 2023-04-27T20:15:01 Z shadow_sami Martian DNA (BOI18_dna) C++17
68 / 100
 2000 ms 144484 KB 
#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];
vi ind[mx];
deque<ll> dq[mx];

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;
		fip(1,n+1){
			cin>>a[i],tnc[i] = -1;
		}
		vi v;
		fip(0,q){
			cin>>tp>>tp2;
			tnc[tp] = tp2;
			v.push_back(tp);
		}
		ans = 1e9;
		fip(1,n+1){
			if(tnc[a[i]]!=-1){
				dq[a[i]].push_back(i);
				if(dq[a[i]].size()>tnc[a[i]])
					dq[a[i]].pop_front();
			}		
			f = 0;
			fx(v){
				if(tnc[x] != dq[x].size())
					f = 1;
			}
			if(f)
				continue;
			tp = 1e18;
			fx(v){
				tp = min(tp,dq[x].front());
			}
			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";
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:59:23: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   59 |     if(dq[a[i]].size()>tnc[a[i]])
      |        ~~~~~~~~~~~~~~~^~~~~~~~~~
dna.cpp:64:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(tnc[x] != dq[x].size())
      |        ~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 139596 KB Output is correct
2 Correct 79 ms 139648 KB Output is correct
3 Correct 80 ms 139624 KB Output is correct
4 Correct 81 ms 139540 KB Output is correct
5 Correct 79 ms 139644 KB Output is correct
6 Correct 81 ms 139600 KB Output is correct
7 Correct 77 ms 139580 KB Output is correct
8 Correct 79 ms 139596 KB Output is correct
9 Correct 83 ms 139648 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 139652 KB Output is correct
2 Correct 93 ms 139684 KB Output is correct
3 Correct 79 ms 139700 KB Output is correct
4 Correct 81 ms 139724 KB Output is correct
5 Correct 82 ms 139676 KB Output is correct
6 Correct 82 ms 139660 KB Output is correct
7 Correct 80 ms 139652 KB Output is correct
8 Correct 80 ms 139656 KB Output is correct
9 Correct 82 ms 139544 KB Output is correct
10 Correct 82 ms 139624 KB Output is correct
11 Correct 79 ms 139628 KB Output is correct
12 Correct 82 ms 139656 KB Output is correct
13 Correct 80 ms 139748 KB Output is correct
14 Correct 81 ms 139556 KB Output is correct
15 Correct 79 ms 139600 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 143644 KB Output is correct
2 Correct 97 ms 143180 KB Output is correct
3 Correct 103 ms 142888 KB Output is correct
4 Correct 112 ms 143332 KB Output is correct
5 Correct 103 ms 142924 KB Output is correct
6 Correct 109 ms 144484 KB Output is correct
7 Correct 110 ms 142936 KB Output is correct
8 Correct 105 ms 142844 KB Output is correct
9 Correct 105 ms 142812 KB Output is correct
10 Correct 113 ms 143652 KB Output is correct
11 Correct 85 ms 139692 KB Output is correct
12 Correct 93 ms 139668 KB Output is correct
13 Correct 80 ms 139856 KB Output is correct
14 Correct 83 ms 139724 KB Output is correct
15 Correct 79 ms 139736 KB Output is correct
16 Correct 79 ms 139680 KB Output is correct
17 Correct 80 ms 139544 KB Output is correct
18 Correct 82 ms 139624 KB Output is correct
19 Correct 81 ms 139600 KB Output is correct
20 Correct 80 ms 139596 KB Output is correct
21 Correct 82 ms 139576 KB Output is correct
22 Correct 81 ms 139580 KB Output is correct
23 Correct 78 ms 139656 KB Output is correct
24 Correct 83 ms 139644 KB Output is correct
25 Correct 78 ms 139648 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 144044 KB Time limit exceeded
2 Halted 0 ms 0 KB -