Submission #769180

#	Time	Username	Problem	Language	Result	Execution time	Memory
769180		Andrey	Stove (JOI18_stove)	C++14	0 / 100	44 ms	70220 KiB

stove

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50