QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277748#6675. DS Team Selection 2ucup-team191WA 7ms60432kbC++146.0kb2023-12-06 22:17:442023-12-06 22:17:44

Judging History

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

  • [2023-12-06 22:17:44]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:60432kb
  • [2023-12-06 22:17:44]
  • 提交

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'