제출 #513453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513453		79brue	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	453 ms	83568 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

struct segTree{
    int n;
    vector<int> tree;
    vector<int> indices;

    void init(int i, int l, int r, vector<int>& vec){
        if(l==r){
            tree[i] = vec[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, vec), init(i*2+1, m+1, r, vec);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void init(vector<int>& vec, vector<int>& idx){
        n = (int)vec.size();
        tree.resize(n*4+1);
        indices = idx;
        init(1, 0, n-1, vec);
    }

    int query(int i, int l, int r, int s, int x){ /// s 이상 index에서 처음으로 x 이하로 떨어지는 지점
        if(r<s || tree[i] > x) return INF;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = query(i*2, l, m, s, x);
        return tmp == INF ? query(i*2+1, m+1, r, s, x) : tmp;
    }

    int query(int s, int x){
        int tmp = query(1, 0, (int)indices.size()-1, lower_bound(indices.begin(), indices.end(), s) - indices.begin(), x);
        if(tmp == INF) return INF;
        return indices[tmp];
    }
} tree[200002];

struct dat{
    int x, y; bool d; /// 0: 진입
    dat(){}
    dat(int x, int y, bool d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        if(y != r.y) return y < r.y;
        return d < r.d;
    }
};

int n;
vector<dat> vec;
int cnt[200002];
int ans;
vector<pair<int, int> > graph[200002];
vector<int> indices[200002];
vector<int> values[200002];
set<pair<int, int> > st;

int offset[200002];

void addToSet(int i, int x){
    int tmp = tree[x].query(i, -offset[x]);
    st.insert(make_pair(tmp, x));
//    printf("Added set %d %d\n", tmp, x);
}

void deleteFromSet(int i, int x){
    int pnt = tree[x].query(i, -offset[x]);
    auto it = st.lower_bound(make_pair(pnt, x));
    assert(it->first == pnt && it->second == x);
//    printf("Deleted set %d %d\n", it->first, it->second);
    st.erase(it);
}

void useOne(int i, int x, int org){
    deleteFromSet(i, x);
    cnt[x]--;
    offset[x]--;
    if(cnt[x]) addToSet(i, x);

    offset[org]++;
    assert(!cnt[org]);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 0));
    }
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 1));
    }
    sort(vec.begin(), vec.end());

    for(int i=1; i<=n; i++) graph[i].push_back(make_pair(-1, 0));
    for(int i=0; i<n+n; i++){
        graph[vec[i].x].push_back(make_pair(i, graph[vec[i].x].back().second + (vec[i].d ? -1 : 1)));
    }
    for(int i=1; i<=n; i++){
        for(auto p: graph[i]) indices[i].push_back(p.first), values[i].push_back(p.second);
        tree[i].init(values[i], indices[i]);
    }

    for(int i=0; i<n+n; i++){
//        printf("i: %d\n", i);
        if(vec[i].d == 0){
            if(cnt[vec[i].x] == 0) addToSet(i, vec[i].x);
            cnt[vec[i].x]++;
            continue;
        }
        if(cnt[vec[i].x]){
            cnt[vec[i].x]--;
            if(cnt[vec[i].x] == 0) deleteFromSet(i, vec[i].x);
            continue;
        }
        ans++;
        assert(!st.empty());
        int key = st.rbegin()->second;
        useOne(i, key, vec[i].x);
    }
    printf("%d", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter2.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40