[BOJ 17082] 쿼리와 쿼리

https://www.acmicpc.net/problem/17082

17082번: 쿼리와 쿼리

Tag : greedy

 

문제요약

배열 L, R에서 각각 구간의 왼쪽 끝, 오른쪽 끝을 뽑아서 구간을 M개 만드는데 

이때 max( 구간의 max )를 최소화 하는게 목표다. 지문에서 max( 구간의 max ) 이런 식으로 설명했는데 

그냥 구간들에서 최대 뽑으라는 말이다.

 

풀이

일단 반드시 포함되는 구간이 있다.

L, R을 정렬했을 때 [L_i, R_i]들은 무슨 짓을 해도 구간에 포함된다.

이것들을 제외하고 다른 점들은 최대한 배제시키는 것이 이득인 것을 쉽게 할 수 있다. 

a < b < c < d일 때 구간 [a, c]와 [b, d]를 고르는 것은 항상 [a, b], [c, d]를 고르는 것보다 이득일 수 없다.

항상 포함되는 구간은 전처리를 할 수 있고 이제 쿼리마다 구간에서 빠지는 값과 새로 들어오는 값을 잘 관리해주면 된다.

 

+ 1등 먹으려고 첨부터 set을 pq로 대체하고 짜다가 디버깅을 몇시간했다

 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, m, q;
int a[202020];
int in[202020];
int ltor[202020];
vector<int> l, r, idx;
vector<pair<int, int>> range;
priority_queue<int> ans;
priority_queue<int> del;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}
char O[2000000],*d=O;
template<class T> inline void p(T x) {
    if(x<0) *d++='-', x=-x;
    char t[16], *q=t;
    do *q++=x%10|48; while(x/=10);
    do *d++=*--q; while(q!=t);
    *d++=10;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    n = f(); m = f(); q = f();
    for(int i=1; i<=n; i++) a[i] = f();
    l.resize(m); r.resize(m);
    for(auto &i : l) i = f();
    for(auto &i : r) i = f();
    sort(l.begin(), l.end()); sort(r.begin(), r.end());
    for(int i=0; i<m; i++) {
        ltor[l[i]] = max(ltor[l[i]], r[i]);
        if(l[i] > r[i]) {
            for(int j=0; j<q; j++) cout << "1000000000" << endl;
            return 0;
        }
    }
    for(int i=1; i<=n; i++) if(ltor[i]) idx.push_back(i);
    for(int i=0,j; i<idx.size(); i=j+1) {
        j = i;
        while(j + 1 < idx.size() and idx[j + 1] <= ltor[idx[j]]) j++;
        range.push_back({idx[i], ltor[idx[j]]});
    }
    for(auto &[l, r] : range) for(int i=l; i<=r; i++) in[i] = 1;
    for(int i=1; i<=n; i++) if(in[i]) ans.push(a[i]);
    while(q--) {
        int x = f(), y = f();
        if(in[x] and in[y] == 0) {
            del.push(a[x]);
            ans.push(a[y]);
        }
        if(in[x] == 0 and in[y]) {
            del.push(a[y]);
            ans.push(a[x]);
        }
        swap(a[x], a[y]);
        while(ans.size() and del.size() and ans.top() == del.top()) {
            ans.pop();
            del.pop();
        }
        cout << ans.top() << endl;
    }
}