Submission #1036494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036494		Andrey	Line Town (CCO23_day1problem3)	C++14	25 / 25	580 ms	333752 KiB

Main

#include<bits/stdc++.h>
using namespace std;

vector<long long> idk(500001);
vector<long long> lol(500001);
vector<long long> no(500001);
vector<pair<long long,long long>> roll(0);

void reset() {
    for(int i = (int)roll.size()-1; i >= 0; i--) {
        lol[roll[i].second] = roll[i].first;
    }
    roll.clear();
}

void upd2(long long a, long long x) {
    while(a < lol.size()) {
        roll.push_back({lol[a],a});
        lol[a]+=x;
        a+=(a&(-a));
    }
}

long long calc2(long long a) {
    long long c = 0,sb = 0;
    for(long long i = 19; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            sb+=lol[c];
        }
    }
    return sb;
}

pair<long long, long long> dude(long long n, vector<long long>& haha, vector<long long>& bruh, long long q) {
    long long ans1 = LLONG_MAX,ans2 = LLONG_MAX;
    reset();
    long long br = n;
    long long s = haha.size()+bruh.size();
    long long y1 = 0,y2 = 0,z1 = (long long)haha.size()-1,z2 = (long long)bruh.size()-1;
    vector<long long> sb1(s+1,-1);
    vector<long long> sb2(s+1,-1);
    sb1[0] = 0;
    sb2[0] = 0;
    vector<pair<long long,long long>> idk1(1,{0,0});
    vector<pair<long long,long long>> idk2(1,{0,0});
    for(long long i = 1; i <= s; i++) {
        long long a;
        if(i%2) {
            if(y1 >= haha.size()) {
                break;
            }
            a = haha[y1];
            y1++;
        }
        else {
            if(y2 >= bruh.size()) {
                break;
            }
            a = bruh[y2];
            y2++;
        }
        upd2(a,-1);
        sb1[i] = sb1[i-1]+calc2(a)+a;
        idk1.push_back({y1,y2});
    }
    reset();
    for(int x: haha) {
        br--;
        upd2(x,1);
    }
    for(int x: bruh) {
        br--;
        upd2(x,1);
    }
    for(long long i = 1; i <= s; i++) {
        long long a;
        if((i+n)%2) {
            if(z1 < 0) {
                break;
            }
            a = haha[z1];
            z1--;
        }
        else {
            if(z2 < 0) {
                break;
            }
            a = bruh[z2];
            z2--;
        }
        sb2[i] = sb2[i-1]+calc2(a)-a+br;
        upd2(a,1);
        idk2.push_back({(long long)haha.size()-z1-1,(long long)bruh.size()-z2-1});
    }
    while(idk1.size() <= s+1) {
        idk1.push_back({-1,-1});
    }
    while(idk2.size() <= s+1) {
        idk2.push_back({-1,-1});
    }
    for(long long i = 0; i <= s; i++) {
        if(sb1[i] != -1 && sb2[s-i] != -1) {
            if(idk1[i].first+idk2[s-i].first == haha.size() && idk1[i].second+idk2[s-i].second == bruh.size()) {
                if(i%2 == 0) {
                    ans1 = min(ans1,sb1[i]+sb2[s-i]);
                }
                else {
                    ans2 = min(ans2,sb1[i]+sb2[s-i]);
                }
            }
        }
    }
    return {ans1,ans2};
}

void upd(long long a, long long x) {
    while(a < idk.size()) {
        idk[a]+=x;
        a+=(a&(-a));
    }
}

long long calc(long long a) {
    long long c = 0,sb = 0;
    for(long long i = 19; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            sb+=idk[c];
        }
    }
    return sb;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,ans = 0;
    cin >> n;
    vector<long long> haha(n+1);
    vector<pair<long long,long long>> wut(0);
    vector<long long> dp0(n+1,LLONG_MAX);
    vector<long long> dp1(n+1,LLONG_MAX);
    dp0[0] = 0;
    for(long long i = 1; i <= n; i++) {
        cin >> haha[i];
        no[i] = haha[i];
        wut.push_back({-abs(haha[i]),i});
    }
    sort(wut.begin(),wut.end());
    for(int i = 0; i < n; i++) {
        wut[i] = {-wut[i].first,wut[i].second};
    }
    for(long long i = 1; i <= n; i++) {
        upd(i,1);
    }
    long long y = 0;
    while(y < n) {
        long long a = wut[y].first;
        if(a == 0) {
            dp0[n] = dp0[y];
            dp1[n] = dp1[y];
        }
        vector<long long> banana1(0);
        vector<long long> banana2(0);
        long long r = n-1;
        for(long long i = y; i < n; i++) {
            if(abs(wut[i].first) != a) {
                r = i-1;
                break;
            }
        }
        for(long long i = y; i <= r; i++) {
            long long c = 0;
            if(haha[wut[i].second] > 0) {
                c = 1;
            }
            if((c+wut[i].second)%2) {
                banana1.push_back(calc(wut[i].second));
            }
            else {
                banana2.push_back(calc(wut[i].second));
            }
        }
        pair<long long,long long> x = dude(n-y,banana1,banana2,a);
        if(dp0[y] != LLONG_MAX) {
            if(x.first != LLONG_MAX) {
                dp0[r+1] = min(dp0[r+1],dp0[y]+x.first);
            }
            if(x.second != LLONG_MAX) {
                dp1[r+1] = min(dp1[r+1],dp0[y]+x.second);
            }
        }
        x = dude(n-y,banana2,banana1,a);
        if(dp1[y] != LLONG_MAX) {
            if(x.first != LLONG_MAX) {
                dp1[r+1] = min(dp1[r+1],dp1[y]+x.first);
            }
            if(x.second != LLONG_MAX) {
                dp0[r+1] = min(dp0[r+1],dp1[y]+x.second);
            }
        }
        for(int i = y; i <= r; i++) {
            upd(wut[i].second,-1);
        }
        y = r+1;
    }
    ans = min(dp0[n],dp1[n]);
    if(ans == LLONG_MAX) {
        cout << -1;
    }
    else {
        cout << ans;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void upd2(long long int, long long int)':
Main.cpp:17:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(a < lol.size()) {
      |           ~~^~~~~~~~~~~~
Main.cpp: In function 'std::pair<long long int, long long int> dude(long long int, std::vector<long long int>&, std::vector<long long int>&, long long int)':
Main.cpp:50:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(y1 >= haha.size()) {
      |                ~~~^~~~~~~~~~~~~~
Main.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if(y2 >= bruh.size()) {
      |                ~~~^~~~~~~~~~~~~~
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   96 |     while(idk1.size() <= s+1) {
      |           ~~~~~~~~~~~~^~~~~~
Main.cpp:99:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   99 |     while(idk2.size() <= s+1) {
      |           ~~~~~~~~~~~~^~~~~~
Main.cpp:104:46: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             if(idk1[i].first+idk2[s-i].first == haha.size() && idk1[i].second+idk2[s-i].second == bruh.size()) {
Main.cpp:104:96: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             if(idk1[i].first+idk2[s-i].first == haha.size() && idk1[i].second+idk2[s-i].second == bruh.size()) {
Main.cpp: In function 'void upd(long long int, long long int)':
Main.cpp:118:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     while(a < idk.size()) {
      |           ~~^~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 3 / 3
• Subtask 7: 2 / 2
• Subtask 8: 3 / 3