QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#221759#7523. Partially Free MealpanhuachaoRE 0ms19992kbC++203.3kb2023-10-21 14:29:352023-10-21 14:29:37

Judging History

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

  • [2023-10-21 14:29:37]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:19992kb
  • [2023-10-21 14:29:35]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int N = 200010;
ll n, ia[N]; pll c[N], a[N];
struct _seg{
    ll rt[N], cnt, son[N<<3][2], l[N<<3], r[N<<3], val[N<<3], sum[N<<3], siz[N<<3];
    ll init(ll ql, ll qr, pll* arr){
        int o = ++cnt;
        l[o] = ql, r[o] = qr;
        val[o] = sum[o] = 0;
        if(ql == qr){
            val[o] = arr[ql].first;
            return o;
        }
        int mid = (ql+qr)/2;
        son[o][0] = init(ql, mid, arr);
        son[o][1] = init(mid+1, qr, arr);
        return o;
    }
    ll revise(ll o, ll pos){
        int u = ++cnt;
        l[u] = l[o], r[u] = r[o], son[u][0] = son[o][0], son[u][1] = son[o][1];
        val[u] = val[o], sum[u] = sum[o], siz[u] = siz[o];
        if(l[o] == r[o]){
            sum[u] = val[u], siz[u] = 1;
            return u;
        }
        int mid = (l[o] + r[o])/2;
        if(pos <= mid) son[u][0] = revise(son[o][0], pos);
                  else son[u][1] = revise(son[o][1], pos);
        sum[u] = sum[son[u][0]] + sum[son[u][1]];
        siz[u] = siz[son[u][0]] + siz[son[u][1]];
        return u;
    }
    ll query(ll o, ll rnk){
        if(rnk == 0) return 0;
        if(l[o] == r[o]) return sum[o];
        if(rnk >= siz[son[o][0]]) return sum[son[o][0]] + query(son[o][1], rnk - siz[son[o][0]]);
                             else return query(son[o][0], rnk);
    }
    void print(ll o){
        printf("%-3lld %-3lld %-3lld %-3lld %-3lld | %-3lld %-3lld %-3lld\n", o, l[o], r[o], son[o][0], son[o][1], val[o], siz[o], sum[o]);
        if(l[o] != r[o]){
            print(son[o][0]); print(son[o][1]);
        }
    }
}tr;
ll g[N], stk[N], tp = 0;

ll calc(ll pos, ll k){
    // printf("in\n");
    ll res = tr.query(tr.rt[pos-1], k-1) + c[pos].first + c[pos].second;
    // printf("out\n");
    return res;
}

int main(){
    scanf("%lld", &n);
    for(ll i = 1; i <= n; i++)
        scanf("%lld%lld", &c[i].second, &c[i].first);
    sort(c+1, c+n+1);
    // for(ll i = 1; i <= n; i++) printf("# b %-3lld a %-3lld\n", c[i].first, c[i].second);
    for(ll i = 1; i <= n; i++)
        a[i] = make_pair(c[i].second, i);
    sort(a+1, a+n+1);
    for(ll i = 1; i <= n; i++) ia[a[i].second] = i;
    // for(ll i = 1; i <= n; i++) printf("$ a %-3lld i %-3lld ia %-3lld\n", a[i].first, a[i].second, ia[i]);

    tr.cnt = 0;
    tr.rt[0] = tr.init(1, n, a);
    // printf("0:Successful\n");
    
    stk[0] = 0;
    for(ll i = 1; i <= n; i++){
        while(tp > 0 && calc(g[tp], stk[tp-1]+1) >= calc(i, stk[tp-1]+1)) tp--;
        if(tp > 0){
            ll l = stk[tp-1]+1, r = g[tp];
            while(l < r){
                int mid = (l+r+1)/2;
                if(calc(g[tp], mid) >= calc(i, mid)) r = mid-1;
                                                else l = mid;
            }
            // printf("%lld %lld %lld %lld\n", i, g[tp], stk[tp-1]+1, l);
            stk[tp] = l;
        }
        tp++; g[tp] = i, stk[tp] = i;
        tr.rt[i] = tr.revise(tr.rt[i-1], ia[i]);
        // printf("%lld:Successful\n", i);
    }
    // tr.print(tr.rt[n-1]);
    ll now = 1;
    for(ll i = 1; i <= n; i++){
        while(i > stk[now]) now++;
        // printf("# %lld %lld\n", g[now], i);
        printf("%lld\n", calc(g[now], i));
    }
    // printf("End\n");
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 19992kb

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

200000
466436993 804989151
660995237 756645598
432103296 703610564
6889895 53276988
873617076 822481192
532911431 126844295
623111499 456772252
937464699 762157133
708503076 786039753
78556972 5436013
582960979 398984169
786333369 325119902
930705057 615928139
924915828 506145001
164984329 208212435...

output:


result: