QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#261600#4428. FenceoogerboogerWA 484ms29720kbC++143.4kb2023-11-23 02:38:372023-11-23 02:38:38

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 02:38:38]
  • 评测
  • 测评结果:WA
  • 用时:484ms
  • 内存:29720kb
  • [2023-11-23 02:38:37]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

#define INF 1000000000
#define INFl 1000000000000000000
#define all(x) x.begin(), x.end()
#define sajz(x) (int)x.size()
#define pb push_back
#define se second
#define fi first
#define yes puts("YES")
#define no puts("NO")
#define erase_duplicates(x) {sort(all(x));(x).resize(distance((x).begin(), unique(all(x))));}
using namespace std;
//using namespace __gnu_pbds;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;
typedef multiset<int> msi;
typedef long double ld;
//typedef cc_hash_table<int, int, hash<int>> ht;

struct Vertex {
	int sz, sum_odd, sum_even;
};

const int N = (1 << 20);

pii a[N];
Vertex t[2*N];
int pods;

void modify(int v, int x, int b) {
	int cnt = x / b;
	int odd = 0, even = 0;
	if (cnt % 2 == 0) {
		odd = cnt * b / 2 + (x % b);
		even = cnt * b / 2;
	} else {
		odd = (cnt + 1) * b / 2;
		even = (cnt - 1) * b / 2 + (x % b);
	}

	t[v += pods] = {(x + b - 1) / b, odd, even};

	// /debug(v, t[v].sz, t[v].sum_odd, t[v].sum_even);

	while (v/2) {
		v/=2;

		if (t[v*2].sz % 2 == 1) {
			t[v] = {t[v*2].sz + t[v*2+1].sz, t[v*2].sum_odd + t[v*2+1].sum_even, t[v*2].sum_even + t[v*2+1].sum_odd};
		} else {
			t[v] = {t[v*2].sz + t[v*2+1].sz, t[v*2].sum_odd + t[v*2+1].sum_odd, t[v*2].sum_even + t[v*2+1].sum_even};
		}
	}
}

void test_case() {
	pods = 1;
	int n;
	cin >> n;
	while (pods <= n) pods *= 2;
	for (int i = 0; i <= pods; i ++) t[i] = {0, 0, 0};

	for (int i = 0; i < n; i ++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a, a + n, greater<pii>());

	for (int b = 1; b <= a[0].first; b ++) {
		int j = 0;
		while (j < n && a[j].first >= b) {
			modify(a[j].second, a[j].first, b);
			j ++;
		}

		cout << t[1].sum_odd << '\n';
	}

	// for (int i = 0; i <= 2*pods; i ++) {
	// 	cout << i << ' ' << t[i].sz << ' ' << t[i].sum_odd << ' ' << t[i].sum_even << '\n';
	// }	
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int t=1;
	cin >> t;
	for (int i = 1; i <= t; i ++) {
		test_case();
	}
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 484ms
memory: 29720kb

input:

5
333834
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

500000
500000
499995
499987
500000
500032
499996
499987
500032
500000
499994
499998
499981
499996
500080
500090
500077
500032
499980
499915
500035
499941
500055
499923
500000
499980
499935
500042
500174
499905
500002
499998
500218
499899
499965
500010
500144
500242
499839
499915
499987
500010
500122...

result:

wrong answer 500001st lines differ - expected: '500000', found: '500001'