oj.uz

답안 #620074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
620074 2022-08-02T21:36:19 Z AlperenT Minerals (JOI19_minerals) C++17
40 / 100
 233 ms 12536 KB 
#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

const int N = 43000 + 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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4432 KB Output is correct
2 Correct 9 ms 4688 KB Output is correct
3 Correct 19 ms 4828 KB Output is correct
4 Correct 36 ms 5804 KB Output is correct
5 Correct 73 ms 6728 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4304 KB Output is correct
2 Correct 2 ms 4304 KB Output is correct
3 Correct 2 ms 4304 KB Output is correct
4 Correct 2 ms 4304 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 9 ms 4688 KB Output is correct
7 Correct 19 ms 4828 KB Output is correct
8 Correct 36 ms 5804 KB Output is correct
9 Correct 73 ms 6728 KB Output is correct
10 Correct 6 ms 4432 KB Output is correct
11 Correct 50 ms 6344 KB Output is correct
12 Correct 71 ms 6768 KB Output is correct
13 Correct 57 ms 6680 KB Output is correct
14 Correct 62 ms 6592 KB Output is correct
15 Incorrect 233 ms 12536 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -