답안 #695349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695349	2023-02-05T04:25:15 Z	Nhoksocqt1	Vudu (COCI15_vudu)	C++17	140 / 140	333 ms	20036 KB

vudu

#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

#	결과	실행 시간	메모리	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