답안 #695348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695348	2023-02-05T04:24:16 Z	Nhoksocqt1	Vudu (COCI15_vudu)	C++17	42 / 140	509 ms	21804 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<int> idx;
int sum[MAXN], 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:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (; i <= idx.size(); i += i & -i)
      |            ~~^~~~~~~~~~~~~

Subtask #1

42.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	500 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Incorrect	509 ms	21088 KB	Output isn't correct
5	Incorrect	265 ms	12108 KB	Output isn't correct
6	Incorrect	410 ms	18684 KB	Output isn't correct
7	Incorrect	458 ms	19428 KB	Output isn't correct
8	Incorrect	315 ms	16932 KB	Output isn't correct
9	Incorrect	455 ms	21804 KB	Output isn't correct
10	Incorrect	442 ms	18964 KB	Output isn't correct