oj.uz

Submission #1113474

# Submission time Handle Problem Language Result Execution time Memory
1113474 2024-11-16T16:05:08 Z jkb_gryz Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 5712 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int base = 1<<20;
int tree[base<<1];

void update(int v, int x){
    v += base;
    tree[v] += x;
    v /= 2;

    while(v){
        tree[v] = tree[2*v] + tree[2*v+1];
        v /= 2;
    }
}

int query(int a, int b){
    a += base - 1;
    b += base + 1;

    int res = 0;
    while(a/2 != b/2){
        if(a % 2 == 0) res += tree[a+1];
        if(b % 2 == 1) res += tree[b-1];
        
        a/=2;
        b/=2;
    }

    return res;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    int n = A.size();
	int Q = X.size();
	vector<int> res(Q);

    map<long long, int> skalowanie;
    for(auto i : A){
        skalowanie[i] = 0;
    }
    for(auto i : V){
        skalowanie[i] = 0;
    }
    int id = 0;

    for(auto &i : skalowanie) i.second = ++id;

    for(auto i : A) update(skalowanie[i], 1);

    for(int i = 0; i < Q; ++i){
        update(skalowanie[A[X[i]]], -1);
        A[X[i]] = V[i];
        update(skalowanie[A[X[i]]], 1);

        int curRes = 0;
        for(int j = 0; j < n; ++j){
            // cerr << j << ": " << query(skalowanie[i]+1, id) << "\n";
            curRes = max(curRes, query(skalowanie[A[j]]+1, id) - (n - j - 1));
        }
        res[i] = curRes;
    }

	return res;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4432 KB Output is correct
2 Correct 37 ms 4688 KB Output is correct
3 Correct 456 ms 4912 KB Output is correct
4 Correct 463 ms 4920 KB Output is correct
5 Correct 436 ms 4912 KB Output is correct
6 Correct 354 ms 4688 KB Output is correct
7 Correct 402 ms 4688 KB Output is correct
8 Correct 433 ms 4920 KB Output is correct
9 Correct 442 ms 4688 KB Output is correct
10 Correct 360 ms 4688 KB Output is correct
11 Correct 329 ms 4688 KB Output is correct
12 Correct 341 ms 4876 KB Output is correct
13 Correct 324 ms 4700 KB Output is correct
14 Correct 366 ms 4940 KB Output is correct
15 Correct 349 ms 4876 KB Output is correct
16 Correct 331 ms 4688 KB Output is correct
17 Correct 327 ms 4688 KB Output is correct
18 Correct 355 ms 4844 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4432 KB Output is correct
2 Correct 37 ms 4688 KB Output is correct
3 Correct 456 ms 4912 KB Output is correct
4 Correct 463 ms 4920 KB Output is correct
5 Correct 436 ms 4912 KB Output is correct
6 Correct 354 ms 4688 KB Output is correct
7 Correct 402 ms 4688 KB Output is correct
8 Correct 433 ms 4920 KB Output is correct
9 Correct 442 ms 4688 KB Output is correct
10 Correct 360 ms 4688 KB Output is correct
11 Correct 329 ms 4688 KB Output is correct
12 Correct 341 ms 4876 KB Output is correct
13 Correct 324 ms 4700 KB Output is correct
14 Correct 366 ms 4940 KB Output is correct
15 Correct 349 ms 4876 KB Output is correct
16 Correct 331 ms 4688 KB Output is correct
17 Correct 327 ms 4688 KB Output is correct
18 Correct 355 ms 4844 KB Output is correct
19 Execution timed out 9039 ms 5712 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2611 ms 4824 KB Output is correct
2 Execution timed out 9055 ms 5456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4432 KB Output is correct
2 Correct 37 ms 4688 KB Output is correct
3 Correct 456 ms 4912 KB Output is correct
4 Correct 463 ms 4920 KB Output is correct
5 Correct 436 ms 4912 KB Output is correct
6 Correct 354 ms 4688 KB Output is correct
7 Correct 402 ms 4688 KB Output is correct
8 Correct 433 ms 4920 KB Output is correct
9 Correct 442 ms 4688 KB Output is correct
10 Correct 360 ms 4688 KB Output is correct
11 Correct 329 ms 4688 KB Output is correct
12 Correct 341 ms 4876 KB Output is correct
13 Correct 324 ms 4700 KB Output is correct
14 Correct 366 ms 4940 KB Output is correct
15 Correct 349 ms 4876 KB Output is correct
16 Correct 331 ms 4688 KB Output is correct
17 Correct 327 ms 4688 KB Output is correct
18 Correct 355 ms 4844 KB Output is correct
19 Execution timed out 9039 ms 5712 KB Time limit exceeded
20 Halted 0 ms 0 KB -