QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277746#6675. DS Team Selection 2ucup-team191#WA 8ms48864kbC++146.0kb2023-12-06 22:17:052023-12-06 22:17:05

Judging History

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

  • [2023-12-06 22:17:05]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:48864kb
  • [2023-12-06 22:17:05]
  • 提交

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'