QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#261600 | #4428. Fence | oogerbooger | WA | 484ms | 29720kb | C++14 | 3.4kb | 2023-11-23 02:38:37 | 2023-11-23 02:38:38 |
Judging History
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'