oj.uz

답안 #735198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735198 2023-05-03T17:08:06 Z shadow_sami Martian DNA (BOI18_dna) C++17
0 / 100
 194 ms 145476 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];
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";
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 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 -