Submission #1243110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243110		eggx50000	Line Town (CCO23_day1problem3)	C++20	0 / 25	6 ms	12100 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

int n, h[500099], c[500099];
int fr[500099], ba[500099];
ll dp[500099][2][2];
bool v[500099][2][2];
vector <int> u, re[500099];

ll f(int k, int s, int e){
    if(k == 0) return 0;
    if(v[k][s][e]) return dp[k][s][e];
    v[k][s][e] = 1;
    dp[k][s][e] = 1e18;
    if(re[k].size() == 0) return f(k - 1, s, e);
    int v = re[k][0];
    if(c[v] == s) dp[k][s][e] = min(dp[k][s][e], f(k - 1, (s + 1) % 2, e) + fr[k]);
    if(c[v] == e) dp[k][s][e] = min(dp[k][s][e], f(k - 1, s, (e + 1) % 2) + ba[k]);
    return dp[k][s][e];
}

struct Few{
    int tr[500099];

    void upd(int a, int v){
        a ++;
        while(a <= n + 1){
            tr[a] += v;
            a += a & -a;
        }
    }

    int qry(int a){
        a ++;
        int s = 0;
        while(a){
            s += tr[a];
            a -= a & -a;
        }
        return s;
    }

} f1, f2;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d",h+i);
        if(h[i] >= 0) c[i] = i % 2;
        else c[i] = (i - 1) % 2;
        h[i] = abs(h[i]);
        u.push_back(h[i]);
    }
    sort(u.begin(), u.end());
    for(int i = 1; i <= n; i ++){
        if(h[i] == 0) continue;
        else h[i] = lower_bound(u.begin(), u.end(), h[i]) - u.begin() + 1;
    }
    for(int i = 1; i <= n; i ++) re[h[i]].push_back(i);
    for(int i = 1; i <= n; i ++){
        f1.upd(h[i], 1);
        fr[i] = f1.qry(h[i] - 1);
    }
    for(int i = n; i >= 1; i --){
        f2.upd(h[i], 1);
        ba[i] = f2.qry(h[i] - 1);
    }
    ll v = f(n, 0, n % 2);
    if(v > 1000000000000000) printf("-1");
    else printf("%lld", v);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d",h+i);
      |         ~~~~~^~~~~~~~~~

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