oj.uz

Submission #128846

# Submission time Handle Problem Language Result Execution time Memory
128846 2019-07-11T10:09:02 Z Osama_Alkhodairy Minerals (JOI19_minerals) C++17
40 / 100
 333 ms 5108 KB 
#include <bits/stdc++.h>
#include "minerals.h"
//~ #include "grader.cpp"
using namespace std;
 
set <int> active; 
vector <int> s, e;
int curl, curr;
int curq;
 
int query(int x){
    if(active.count(x)) active.erase(x);
    else active.insert(x);
    return curq = Query(x);
}
void solve(int l, int r, vector <int> &cur){
    if(r < l) return;
    if(l == r){
        assert(cur.size() == 1);
        Answer(e[l], cur[0]);
        return;
    }
    int mid = (l + r) / 2;
    for(int i = l ; i <= mid ; i++){
        if(active.count(e[i])) continue;
        query(e[i]);
    }
    while(1){
        auto it = active.upper_bound(e[mid]);
        if(it == active.end() || *it > e[r]) break;
        query(*it);
    }
    vector <int> left, right;
    for(auto &i : cur){
        int las = curq;
        int x = query(i);
        if(x == las) left.push_back(i);
        else right.push_back(i);
        //~ query(i);
    }
    solve(l, mid, left);
    solve(mid + 1, r, right);
}
void Solve(int N){
    int prev = 0;
    for(int i = 1 ; i <= 2 * N ; i++){
        int cur = query(i);
        if(cur != prev) s.push_back(i);
        else e.push_back(i);
        prev = cur;
    }
    curl = 0;
    curr = N - 1;
    solve(0, N - 1, s);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 504 KB Output is correct
3 Correct 21 ms 764 KB Output is correct
4 Correct 56 ms 1304 KB Output is correct
5 Correct 99 ms 2168 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 21 ms 764 KB Output is correct
8 Correct 56 ms 1304 KB Output is correct
9 Correct 99 ms 2168 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 2300 KB Output is correct
13 Correct 91 ms 2168 KB Output is correct
14 Correct 73 ms 2168 KB Output is correct
15 Correct 333 ms 5108 KB Output is correct
16 Correct 330 ms 5108 KB Output is correct
17 Incorrect 242 ms 5104 KB Wrong Answer [2]
18 Halted 0 ms 0 KB -