Submission #1268155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268155		TgX_2	Vudu (COCI15_vudu)	C++20	42 / 140	308 ms	12304 KiB

vudu

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

// #define int long long

const int maxn = 1e6 + 7;
int n, p, a[maxn];

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int _n) {
        n = _n;
        bit.assign(n + 5, 0);
    }
    void add(int i, int val) {
        for (; i <= n; i += i & -i) bit[i] += val;
    }
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> p;

    vector<int> val;
    for (int i = 1; i <= n; i++) {
        a[i] -= p;
        a[i] += a[i - 1];
        val.push_back(a[i]);
    }

    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for (int i = 1; i <= n; i++) 
        a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;

    int m = (int)(val.size()) + 1;
    Fenwick fen(m);

    int ans = 0;
    fen.add(lower_bound(val.begin(), val.end(), 0) - val.begin() + 1, 1);
    for (int i = 1; i <= n; i++) {
        ans += fen.sum(a[i]);
        fen.add(a[i], 1);
    }

    cout << ans;

    cerr << "Time : " << clock() * 1.0 / CLOCKS_PER_SEC << " ms." << endl;
    return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("temp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
vudu.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("temp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 42 / 140