oj.uz

Submission #620084

# Submission time Handle Problem Language Result Execution time Memory
620084 2022-08-02T22:14:04 Z AlperenT Minerals (JOI19_minerals) C++17
40 / 100
 215 ms 12916 KB 
#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

const int N = 50000 + 5;

int n, ans[N], ptr, cnt;

vector<int> a, b;

set<int> cur;

int query(int x){
    if(cur.find(x) != cur.end()) cur.erase(x);
    else cur.insert(x);

    return cnt = Query(x);
}

struct SegTree{
    vector<int> tree[N * 4];

    void build(int v = 1, int l = 1, int r = n, bool flag = false){
        if(l == r) ans[l] = tree[v].front();
        else{
            int m = l + (r - l) / 2;

            while(ptr < m){
                ptr++;
                query(a[ptr - 1]);
            }

            while(ptr > m){
                query(a[ptr - 1]);
                ptr--;
            }

            if(l + 1 == r){
                if(flag){
                    int prvcnt = cnt;

                    query(tree[v][0]);

                    if(cnt == prvcnt) tree[v * 2].push_back(tree[v][0]), tree[v * 2 + 1].push_back(tree[v][1]);
                    else tree[v * 2 + 1].push_back(tree[v][0]), tree[v * 2].push_back(tree[v][1]);
                }
                else{
                    int prvcnt = cnt;

                    query(tree[v][0]);

                    if(cnt == prvcnt + 1) tree[v * 2 + 1].push_back(tree[v][0]), tree[v * 2].push_back(tree[v][1]);
                    else tree[v * 2].push_back(tree[v][0]), tree[v * 2 + 1].push_back(tree[v][1]);
                }
            }
            else{
                if(flag){
                    for(auto x : tree[v]){
                        int prvcnt = cnt;

                        query(x);

                        if(cnt == prvcnt) tree[v * 2].push_back(x);
                        else tree[v * 2 + 1].push_back(x);
                    }
                }
                else{
                    for(auto x : tree[v]){
                        int prvcnt = cnt;

                        query(x);

                        if(cnt == prvcnt + 1) tree[v * 2 + 1].push_back(x);
                        else tree[v * 2].push_back(x);
                    }
                }
            }

            build(v * 2 + 1, m + 1, r, flag ^ 1);
            build(v * 2, l, m, flag ^ 1);
        }
    }
};

SegTree sgt;

void Solve(int N_) {
    n = N_;

    for(int i = 1; i <= n * 2; i++){
        int prvcnt = cnt;

        query(i);

        if(cnt == prvcnt + 1) a.push_back(i);
        else{
            query(i);
            b.push_back(i);
        }
    }

    for(auto x : a) query(x);

    for(auto x : b) sgt.tree[1].push_back(x);

    sgt.build();

    for(int i = 1; i <= n; i++) Answer(a[i - 1], ans[i]);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5072 KB Output is correct
2 Correct 12 ms 5328 KB Output is correct
3 Correct 17 ms 5620 KB Output is correct
4 Correct 35 ms 6292 KB Output is correct
5 Correct 72 ms 7652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 6 ms 5072 KB Output is correct
6 Correct 12 ms 5328 KB Output is correct
7 Correct 17 ms 5620 KB Output is correct
8 Correct 35 ms 6292 KB Output is correct
9 Correct 72 ms 7652 KB Output is correct
10 Correct 5 ms 5072 KB Output is correct
11 Correct 47 ms 6940 KB Output is correct
12 Correct 76 ms 7716 KB Output is correct
13 Correct 61 ms 7652 KB Output is correct
14 Correct 62 ms 7528 KB Output is correct
15 Incorrect 215 ms 12916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -