QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277746 | #6675. DS Team Selection 2 | ucup-team191# | WA | 8ms | 48864kb | C++14 | 6.0kb | 2023-12-06 22:17:05 | 2023-12-06 22:17:05 |
Judging History
answer
#include <bits/stdc++.h>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < ll, ll > pt;
const int N = 2e5 + 500;
const int OFF = (1 << 18);
ll ccw(pt A, pt B, pt C) {
return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}
struct node{
int fir, lst, brj;
ll sum_ind, sum_val;
ll max_val, min_val;
node(){
fir = -1; lst = -1; brj = 0;
sum_ind = 0; sum_val = 0;
max_val = 0; min_val= 0 ;
}
};
node mrg(node A, node B) {
if(A.brj == 0) return B;
if(B.brj == 0) return A;
node C;
C.fir = A.fir; C.min_val = A.min_val;
C.lst = B.lst; C.max_val = B.max_val;
C.brj = A.brj + B.brj;
C.sum_ind = A.sum_ind + B.sum_ind;
C.sum_val = A.sum_val + B.sum_val;
return C;
}
int prop_ind[2 * OFF];
ll prop_set[2 * OFF];
node T[2 * OFF];
void refresh(int x) {
if(T[x].fir == -1) return;
if(prop_set[x] != -1) {
T[x].min_val = prop_set[x]; T[x].max_val = prop_set[x];
T[x].sum_val = prop_set[x] * T[x].brj;
if(x < OFF) {
prop_ind[2 * x] = 0; prop_ind[2 * x + 1] = 0;
prop_set[2 * x] = prop_set[x];
prop_set[2 * x + 1] = prop_set[x];
}
prop_set[x] = -1;
}
if(prop_ind[x]) {
T[x].min_val += (ll)T[x].fir * prop_ind[x];
T[x].max_val += (ll)T[x].lst * prop_ind[x];
T[x].sum_val += (ll)T[x].sum_ind * prop_ind[x];
if(x < OFF) {
prop_ind[2 * x] += prop_ind[x];
prop_ind[2 * x + 1] += prop_ind[x];
}
prop_ind[x] = 0;
}
}
void set_val(int i, int a, int b, ll v) {
refresh(i);
if(T[i].min_val > v) {
prop_ind[i] = 0; prop_set[i] = v;
refresh(i); return;
}
if(T[i].fir == -1 || T[i].max_val <= v) return;
set_val(2 * i, a, (a + b) / 2, v);
set_val(2 * i + 1, (a + b) / 2 + 1, b, v);
T[i] = mrg(T[2 * i], T[2 * i + 1]);
}
ll query(int i, int a, int b, int lo, int hi) {
refresh(i);
if(lo <= a && b <= hi) return T[i].sum_val;
if(a > hi || b < lo) return 0;
return query(2 * i, a, (a + b) / 2, lo, hi) + query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}
void ubaci(int i, int a, int b, int gdje, ll sto) {
refresh(i);
if(a == b) {
T[i].fir = a; T[i].lst = a; T[i].brj = 1;
T[i].sum_ind = a; T[i].sum_val = sto;
T[i].max_val = sto; T[i].min_val = sto;
return;
}
if(gdje <= (a + b) / 2)
ubaci(2 * i, a, (a + b) / 2, gdje, sto), refresh(2 * i + 1);
else
ubaci(2 * i + 1, (a + b) / 2 + 1, b, gdje, sto), refresh(2 * i);
T[i] = mrg(T[2 * i], T[2 * i + 1]);
}
ll ob_T[2 * OFF], ind_T[2 * OFF];
ll vrijeme = 0;
void ob_delete(int i) {
ob_T[OFF + i] = 0; ind_T[OFF + i] = 0;
for(i = (i + OFF) / 2; i ; i /= 2) {
ob_T[i] = ob_T[2 * i] + ob_T[2 * i + 1];
ind_T[i] = ind_T[2 * i] + ind_T[2 * i + 1];
}
}
ll query2(int i, int a, int b, int lo, int hi) {
if(lo <= a && b <= hi) return ob_T[i] + ind_T[i] * vrijeme;
if(a > hi || b < lo) return 0;
return query2(2 * i, a, (a + b) / 2, lo, hi) + query2(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}
struct convex_hull {
vector < pt > v;
void ubaci(pt A) {
if(!v.empty() && A.X == v.back().X) {
if(A.Y >= v.back().Y)
return;
else {
v.pop_back();
}
}
while((int)v.size() >= 2 && ccw(v[(int)v.size() - 2], v[(int)v.size() - 1], A) <= 0) {
v.pop_back();
}
v.PB(A);
}
ll query(ll x) {
ll ans = v[0].X * x + v[0].Y;
int lo = 0, hi = (int)v.size() - 1;
while(lo < hi) {
int mid = (lo + hi) / 2;
ll v1 = v[mid].X * x + v[mid].Y;
ll v2 = v[mid + 1].X * x +v[mid + 1].Y;
if(v1 < v2) ans = min(ans, v1), hi = mid;
else ans = min(ans, v2), lo = mid + 1;
}
return ans;
}
};
int n, q, kad[N], lo[N], hi[N], mid[N];
vector< int > immi[N];
ll A[N];
int q_ty[N];
ll q_val[N];
int q_l[N], q_r[N];
vector < int > izb[N];
int main(){
memset(prop_set, -1, sizeof(prop_set));
scanf("%d%d", &n, &q);
for(int i = 1;i <= n;i++) {
scanf("%lld", A + i);
ob_T[i] = A[i]; ind_T[i] = i;
}
for(int i = OFF - 1; i ; i--)
ob_T[i] = ob_T[2 * i] + ob_T[2 * i + 1], ind_T[i] = ind_T[2 * i] + ind_T[2 * i + 1];
for(int i = 0;i < q;i++) {
scanf("%d", q_ty + i);
if(q_ty[i] == 1) {
scanf("%lld", q_val + i);
} else if(q_ty[i] == 3) {
scanf("%d%d", q_l + i, q_r + i);
}
}
for (int i=1;i<=n;++i) lo[i]=0,hi[i]=q-1;
convex_hull conv;
for (int z=0;z<18;++z)
{
conv.v.clear();
for (int i=0;i<q;++i) immi[i].clear();
for (int i=1;i<=n;++i)
{
mid[i]=(lo[i]+hi[i])/2;
immi[mid[i]].push_back(i);
}
int ci=0;
for (int i=0;i<q;++i)
{
if (q_ty[i]==2) ++ci;
if (q_ty[i]==1) conv.ubaci({-ci,q_val[i]});
for (auto x: immi[i])
{
ll re=conv.query(x),z=A[x];
if (re<z) hi[x]=mid[x];
else lo[x]=mid[x]+1;
}
}
}
for(int i = 1;i <= n;i++) {
//printf("%d\n",mid[i]);
//int x; scanf("%d", &x);
izb[lo[i]].PB(i);
}
// DODIN PRECOMPUTE
for(int i = 0;i < q;i++) {
if(q_ty[i] == 3) {
printf("%lld\n", query(1, 0, OFF - 1, q_l[i], q_r[i]) + query2(1, 0, OFF - 1, q_l[i], q_r[i]));
} else if(q_ty[i] == 2) {
vrijeme++; prop_ind[1]++;
} else {
set_val(1, 0, OFF - 1, q_val[i]);
for(int x : izb[i]) {
ubaci(1, 0, OFF - 1, x, q_val[i]);
ob_delete(x);
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 48500kb
input:
13 11 6 14 14 6 3 6 4 13 10 3 12 5 11 1 2 2 2 2 1 11 3 4 6 2 1 6 2 1 9 3 2 13
output:
33 107
result:
ok 2 number(s): "33 107"
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 48864kb
input:
5000 5000 29940 259997 53132 912489 608312 594283 432259 344137 889466 383028 320097 337418 571199 372832 563110 542407 133378 998389 238387 120880 477310 634888 191990 133585 935315 558139 141724 893331 190118 991968 843042 384930 935256 891482 123419 91431 955722 376987 197566 106433 234494 645967...
output:
289016717 247308515 71536266 190497610 119795788 18693568 99023406 121798482 91482218 15499803 140385806 142015247 73255600 944484 150602484 130979600 10008129 58717988 11248629 13653458 30703440 40038616 14364264 50837280 17321506 26317000 667716 31026000 55967946 5188989 34580556 7820514 77250421 ...
result:
wrong answer 1st numbers differ - expected: '512185934', found: '289016717'