답안 #695348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695348 2023-02-05T04:24:16 Z Nhoksocqt1 Vudu (COCI15_vudu) C++17
42 / 140
509 ms 21804 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<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)
      |            ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 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