oj.uz

Submission #513453

# Submission time Handle Problem Language Result Execution time Memory
513453 2022-01-17T06:35:39 Z 79brue None (JOI16_worst_reporter2) C++14
100 / 100
 453 ms 83568 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){
        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);
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25292 KB Output is correct
2 Correct 11 ms 25256 KB Output is correct
3 Correct 12 ms 25292 KB Output is correct
4 Correct 11 ms 25292 KB Output is correct
5 Correct 11 ms 25316 KB Output is correct
6 Correct 14 ms 25344 KB Output is correct
7 Correct 14 ms 25356 KB Output is correct
8 Correct 12 ms 25292 KB Output is correct
9 Correct 12 ms 25336 KB Output is correct
10 Correct 12 ms 25296 KB Output is correct
11 Correct 12 ms 25292 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25292 KB Output is correct
2 Correct 11 ms 25256 KB Output is correct
3 Correct 12 ms 25292 KB Output is correct
4 Correct 11 ms 25292 KB Output is correct
5 Correct 11 ms 25316 KB Output is correct
6 Correct 14 ms 25344 KB Output is correct
7 Correct 14 ms 25356 KB Output is correct
8 Correct 12 ms 25292 KB Output is correct
9 Correct 12 ms 25336 KB Output is correct
10 Correct 12 ms 25296 KB Output is correct
11 Correct 12 ms 25292 KB Output is correct
12 Correct 12 ms 25344 KB Output is correct
13 Correct 12 ms 25360 KB Output is correct
14 Correct 14 ms 25256 KB Output is correct
15 Correct 12 ms 25356 KB Output is correct
16 Correct 11 ms 25292 KB Output is correct
17 Correct 12 ms 25296 KB Output is correct
18 Correct 12 ms 25304 KB Output is correct
19 Correct 14 ms 25352 KB Output is correct
20 Correct 12 ms 25332 KB Output is correct
21 Correct 12 ms 25356 KB Output is correct
22 Correct 12 ms 25292 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25292 KB Output is correct
2 Correct 11 ms 25256 KB Output is correct
3 Correct 12 ms 25292 KB Output is correct
4 Correct 11 ms 25292 KB Output is correct
5 Correct 11 ms 25316 KB Output is correct
6 Correct 14 ms 25344 KB Output is correct
7 Correct 14 ms 25356 KB Output is correct
8 Correct 12 ms 25292 KB Output is correct
9 Correct 12 ms 25336 KB Output is correct
10 Correct 12 ms 25296 KB Output is correct
11 Correct 12 ms 25292 KB Output is correct
12 Correct 12 ms 25344 KB Output is correct
13 Correct 12 ms 25360 KB Output is correct
14 Correct 14 ms 25256 KB Output is correct
15 Correct 12 ms 25356 KB Output is correct
16 Correct 11 ms 25292 KB Output is correct
17 Correct 12 ms 25296 KB Output is correct
18 Correct 12 ms 25304 KB Output is correct
19 Correct 14 ms 25352 KB Output is correct
20 Correct 12 ms 25332 KB Output is correct
21 Correct 12 ms 25356 KB Output is correct
22 Correct 12 ms 25292 KB Output is correct
23 Correct 17 ms 26628 KB Output is correct
24 Correct 18 ms 26580 KB Output is correct
25 Correct 18 ms 26580 KB Output is correct
26 Correct 19 ms 26572 KB Output is correct
27 Correct 18 ms 26676 KB Output is correct
28 Correct 16 ms 26700 KB Output is correct
29 Correct 17 ms 26692 KB Output is correct
30 Correct 17 ms 26644 KB Output is correct
31 Correct 18 ms 26704 KB Output is correct
32 Correct 15 ms 26632 KB Output is correct
33 Correct 16 ms 26704 KB Output is correct
34 Correct 17 ms 26700 KB Output is correct
35 Correct 21 ms 26688 KB Output is correct
36 Correct 18 ms 26708 KB Output is correct
37 Correct 16 ms 26764 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25292 KB Output is correct
2 Correct 11 ms 25256 KB Output is correct
3 Correct 12 ms 25292 KB Output is correct
4 Correct 11 ms 25292 KB Output is correct
5 Correct 11 ms 25316 KB Output is correct
6 Correct 14 ms 25344 KB Output is correct
7 Correct 14 ms 25356 KB Output is correct
8 Correct 12 ms 25292 KB Output is correct
9 Correct 12 ms 25336 KB Output is correct
10 Correct 12 ms 25296 KB Output is correct
11 Correct 12 ms 25292 KB Output is correct
12 Correct 12 ms 25344 KB Output is correct
13 Correct 12 ms 25360 KB Output is correct
14 Correct 14 ms 25256 KB Output is correct
15 Correct 12 ms 25356 KB Output is correct
16 Correct 11 ms 25292 KB Output is correct
17 Correct 12 ms 25296 KB Output is correct
18 Correct 12 ms 25304 KB Output is correct
19 Correct 14 ms 25352 KB Output is correct
20 Correct 12 ms 25332 KB Output is correct
21 Correct 12 ms 25356 KB Output is correct
22 Correct 12 ms 25292 KB Output is correct
23 Correct 17 ms 26628 KB Output is correct
24 Correct 18 ms 26580 KB Output is correct
25 Correct 18 ms 26580 KB Output is correct
26 Correct 19 ms 26572 KB Output is correct
27 Correct 18 ms 26676 KB Output is correct
28 Correct 16 ms 26700 KB Output is correct
29 Correct 17 ms 26692 KB Output is correct
30 Correct 17 ms 26644 KB Output is correct
31 Correct 18 ms 26704 KB Output is correct
32 Correct 15 ms 26632 KB Output is correct
33 Correct 16 ms 26704 KB Output is correct
34 Correct 17 ms 26700 KB Output is correct
35 Correct 21 ms 26688 KB Output is correct
36 Correct 18 ms 26708 KB Output is correct
37 Correct 16 ms 26764 KB Output is correct
38 Correct 453 ms 73960 KB Output is correct
39 Correct 400 ms 78664 KB Output is correct
40 Correct 369 ms 78696 KB Output is correct
41 Correct 417 ms 78636 KB Output is correct
42 Correct 424 ms 83568 KB Output is correct
43 Correct 247 ms 81384 KB Output is correct
44 Correct 279 ms 81388 KB Output is correct
45 Correct 263 ms 81404 KB Output is correct
46 Correct 278 ms 81260 KB Output is correct
47 Correct 196 ms 82452 KB Output is correct
48 Correct 243 ms 79548 KB Output is correct
49 Correct 204 ms 79460 KB Output is correct
50 Correct 258 ms 79620 KB Output is correct
51 Correct 278 ms 79596 KB Output is correct
52 Correct 202 ms 79404 KB Output is correct