oj.uz

Submission #513410

# Submission time Handle Problem Language Result Execution time Memory
513410 2022-01-17T06:07:01 Z 79brue None (JOI16_worst_reporter2) C++14
0 / 100
 15 ms 25420 KB 
#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){
        return query(1, 0, (int)indices.size()-1, lower_bound(indices.begin(), indices.end(), s) - indices.begin(), x);
    }
} 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){
    st.insert(make_pair(tree[x].query(i, -offset[x]), x));
}

void deleteFromSet(int i, int x){
    auto it = st.lower_bound(make_pair(tree[x].query(i, -offset[x]), x));
    assert(it->second == x);
    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++){
        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);
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25292 KB Output is correct
2 Correct 15 ms 25256 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 13 ms 25292 KB Output is correct
5 Correct 13 ms 25292 KB Output is correct
6 Correct 13 ms 25360 KB Output is correct
7 Correct 13 ms 25312 KB Output is correct
8 Incorrect 15 ms 25268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25292 KB Output is correct
2 Correct 15 ms 25256 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 13 ms 25292 KB Output is correct
5 Correct 13 ms 25292 KB Output is correct
6 Correct 13 ms 25360 KB Output is correct
7 Correct 13 ms 25312 KB Output is correct
8 Incorrect 15 ms 25268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25292 KB Output is correct
2 Correct 15 ms 25256 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 13 ms 25292 KB Output is correct
5 Correct 13 ms 25292 KB Output is correct
6 Correct 13 ms 25360 KB Output is correct
7 Correct 13 ms 25312 KB Output is correct
8 Incorrect 15 ms 25268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25292 KB Output is correct
2 Correct 15 ms 25256 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 13 ms 25292 KB Output is correct
5 Correct 13 ms 25292 KB Output is correct
6 Correct 13 ms 25360 KB Output is correct
7 Correct 13 ms 25312 KB Output is correct
8 Incorrect 15 ms 25268 KB Output isn't correct
9 Halted 0 ms 0 KB -