oj.uz

Submission #695349

# Submission time Handle Problem Language Result Execution time Memory
695349 2023-02-05T04:25:15 Z Nhoksocqt1 Vudu (COCI15_vudu) C++17
140 / 140
 333 ms 20036 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

const int MAXN = 1000006;

vector<ll> idx;
ll sum[MAXN];
int fen[MAXN], numDay, P;

void modify(int i, int v) {
    for (; i <= idx.size(); i += i & -i)
        fen[i] += v;
}

int get(int i) {
    int res(0);
    for (; i > 0; i -= i & -i)
        res += fen[i];

    return res;
}

void process() {
    cin >> numDay;
    for (int i = 1; i <= numDay; ++i)
        cin >> sum[i];

    cin >> P;
    for (int i = 1; i <= numDay; ++i) {
        sum[i] += sum[i - 1] - P;
        idx.push_back(sum[i]);
    }

    idx.push_back(0);
    sort(idx.begin(), idx.end());
    idx.erase(unique(idx.begin(), idx.end()), idx.end());

    int pos = upper_bound(idx.begin(), idx.end(), 0) - idx.begin();
    modify(pos, 1);

    ll res(0);
    for (int i = 1; i <= numDay; ++i) {
        int pos = upper_bound(idx.begin(), idx.end(), sum[i]) - idx.begin();
        res += get(pos);
        modify(pos, 1);
    }

    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("vudu.inp", "r", stdin);
//    freopen("vudu.out", "w", stdout);

    process();
    return 0;
}

Compilation message

vudu.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
vudu.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
vudu.cpp: In function 'void modify(int, int)':
vudu.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (; i <= idx.size(); i += i & -i)
      |            ~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 333 ms 19512 KB Output is correct
5 Correct 197 ms 12968 KB Output is correct
6 Correct 281 ms 17332 KB Output is correct
7 Correct 297 ms 17912 KB Output is correct
8 Correct 258 ms 15644 KB Output is correct
9 Correct 310 ms 20036 KB Output is correct
10 Correct 270 ms 17556 KB Output is correct