문제
https://www.acmicpc.net/problem/17163
17163번: 가희의 수열놀이 (Large)
첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 106, 1 ≤ mod ≤ 2×109) 이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어집니다. 이는 맨 앞에 오는 정수의 값 (1, 2, 3)에 따라 구분됩니다. 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 231-1) 2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 만약 arr이 비어
www.acmicpc.net
풀이
만약 mod가 query개수 보다 많다면 항상 불가능하므로, -1을 출력한다.
mod가 query개수보다 작은 경우에는 0~mod-1까지의 index를 가지는 stack을 만들어보자.
그리고 숫자가 새로 들어올때 마다, 해당하는 나머지를 index로 가지는 stack에 현재 arr의 원소의 개수를 넣어준다.
3 query가 들어왔을 때, 각 나머지 별로 stack의 top에 있는 숫자의 min값이 우리가 찾는 index가 되고, 전체 사이즈에서 찾은 값을 빼주면 답이 된다.
이 방식으로 구하면 $O(q\times mod)$의 시간복잡도가 걸리지만 segment tree를 이용하면 $O(mod+q log mod)$의 시간복잡도로 원하는 답을 구할 수 있다.
Time Complexity : $O(mod+q log mod)$
코드
#include<iostream>
#include<vector>
#include<stack>
#define N 1000000
#define INF 1<<30
using namespace std;
stack<int, vector<int> > S;
stack<int, vector<int> > rem[N];
int seg[1<<21];
int p, q, mod;
void update(int t)
{
t+=p;
while(t!=1)
{
t>>=1;
seg[t] = min(seg[t<<1], seg[t<<1|1]);
}
}
int main()
{
cin.tie(NULL);
cin.sync_with_stdio(false);
cin>>q>>mod;
for(p=mod;p^(-p&p);p+=(-p&p));
if(mod>q)
{
while(q--)
{
int x;
cin>>x;
if(x==3) cout<<-1<<"\n";
if(x==1) cin>>x;
}
return 0;
}
for(int i=p;i<p<<1;i++) seg[i]=i<p+mod?-1:INF;
for(int i=p-1;i>0;i--) seg[i] = min(seg[i<<1],seg[i<<1|1]);
while(q--)
{
int x;
cin>>x;
if(x==1)
{
cin>>x;
int t=x%mod;
S.push(t);
rem[t].push(S.size());
seg[p+t]=S.size();
update(t);
}
else if(x==2)
{
if(S.empty())continue;
int t = S.top();
S.pop();
rem[t].pop();
seg[p+t]=rem[t].empty()?-1:rem[t].top();
update(t);
}
else
{
if(seg[1]==-1) cout<<"-1\n";
else cout<< S.size()-seg[1]+1<<"\n";
}
}
}'PS > BOJ' 카테고리의 다른 글
| [BOJ] 16000. 섬 (0) | 2019.05.06 |
|---|---|
| [BOJ] 5698. Tautogram (0) | 2019.05.06 |
| [BOJ] 9521. 색칠 공부 (2) | 2019.05.06 |
| [BOJ] 1734. 교통 체계 (0) | 2019.05.02 |
| [BOJ] 1849. 순열 (0) | 2019.05.01 |
