oj.uz

Submission #769180

# Submission time Handle Problem Language Result Execution time Memory
769180 2023-06-29T09:28:34 Z Andrey Stove (JOI18_stove) C++14
0 / 100
 44 ms 70220 KB 
#include <bits/stdc++.h>
using namespace std;

long long haha[200001][19];

void add(long long a) {
    for(long long i = 0; i < 19; i++) {
        a-=(a%(1 << i));
        haha[a][i]++;
    }
}

long long calc(long long a, long long b) {
    long long j = 0;
    long long ans = 0;
    while(a < b) {
        j = 0;
        while(a%(1 << j) == 0 && a+(1 << j) <= b) {
            j++;
        }
        j--;
        ans+=haha[a][j];
        a+=(1 << j);
    }
    return ans+haha[b][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    const long long y = 100000;
    long long n,p,a,ans = 0;
    cin >> n;
    for(long long i = 0; i < 200001; i++) {
        for(long long j = 0; j < 19; j++) {
            haha[i][j] = 0;
        }
    }
    vector<long long> bruh(2*n);
    vector<vector<long long>> yeah(200001);
    for(long long i = 0; i < 2*n; i++) {
        cin >> bruh[i];
    }
    for(long long i = 2*n-1; i >= 0; i--) {
        yeah[bruh[i]+y].push_back(i);
    }
    for(long long i = 0; i < 2*n; i++) {
        if(bruh[i] != -INT_MAX) {
            while(yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1] < i) {
                yeah[-bruh[i]+y].pop_back();
            }
            if(bruh[i] < 0) {
                p = yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1];
                a = 0;
            }
            else {
                p = yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1];
                a = 1;
            }
            yeah[-bruh[i]+y].pop_back();
            bruh[p] = -INT_MAX;
            ans += p-i-1-calc(i,p-1)+a;
            add(p);
            add(i);
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 70220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 70220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 70220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -