QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277748 | #6675. DS Team Selection 2 | ucup-team191 | WA | 7ms | 60432kb | C++14 | 6.0kb | 2023-12-06 22:17:44 | 2023-12-06 22:17:44 |
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: 60432kb
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: 4ms
memory: 60120kb
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 331125743 275971066 43378840 227330236 283607928 209829676 39499020 322018917 325129189 171651018 2046222 267117772 213429915 20480211 108282333 21889512 34631220 55848925 92345967 36949030 86469096 43439237 50829332 1334865 76050896 114623436 13564322 79974466 15230088 ...
result:
wrong answer 1st numbers differ - expected: '512185934', found: '289016717'