oj.uz

Submission #978488

# Submission time Handle Problem Language Result Execution time Memory
978488 2024-05-09T09:04:07 Z sleepntsheep Fish 3 (JOI24_fish3) C
100 / 100
 562 ms 52820 KB 
#include<stdio.h>
#include<stdlib.h>

#define N 300000

#define Q 300000

int n, q, *eh[N+1], eo[N+1];
long long d,ans[Q];

void push(int i,int j)
{
    int o=eo[i]++;
    if(!o)eh[i]=(int*)malloc(2*sizeof**eh);
    else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}


/*
 * sweep from left to right,
 *
 * decompose fishes to dominoes
 *
 * amortized O(n) dominoes move
 *
 *
 * need segtree that can 
 * decrease k from a[l..r], add k to b[l..r]
 * point query a[i]
 * range query b[l..r]
 */

#define N_ (((N+1)<<2)+1)
long long ta[N_], la[N_], tb[N_], lb[N_], c;

int dominoes[N+1], top;

void pul(int v,int l,int r)
{
    long long m=l+(r-l)/2, w1=m-l+1, w2=r-m;
    ta[v] = ta[2*v] +  ta[2*v+1] + w1 * la[2*v] + w2 * la[2*v+1];
    tb[v] = tb[2*v] +  tb[2*v+1] + w1 * lb[2*v] + w2 * lb[2*v+1];
}

void add(int x,int y,long long k,long long k2,int v,int l,int r)
{
    if (r < x || y < l) return;
    if (x <= l && r <= y)
    {
        la[v] += k;
        lb[v] += k2;
        return;
    }
    add(x, y, k, k2, 2*v, l, l+(r-l)/2);
    add(x, y, k, k2, 2*v+1, l+(r-l)/2+1, r);
    pul(v, l, r);
}
void add_(int x,int y,long long k,long long k2) { add(x, y, k, k2, 1, 0, n); }

long long query1(int p,int v,int l,int r)
{
    if(l==r)return ta[v] + la[v];
    return la[v] + (p <= l+(r-l)/2 ? query1(p,2*v,l,l+(r-l)/2): query1(p,2*v+1,l+(r-l)/2+1,r));
}
long long query1_(int p) { return query1(p, 1, 0, n); }

int max(int i,int j){return i>j?i:j;}
int min(int i,int j){return i<j?i:j;}
int overlap(int x,int y,int a, int b) { return(y<a||b<x)? 0:min(b,y)-max(x,a)+1; }

long long query2(int x,int y,int v,int l,int r)
{
    if(r<x||y<l)return 0;
    if (x<=l&&r<=y) return lb[v] * (r-l+1ll) + tb[v];
    return lb[v] * overlap(x,y,l,r) + query2(x, y, 2*v, l, l+(r-l)/2) + query2(x, y, 2*v+1, l+(r-l)/2+1, r);
}
long long query2_(int x,int y) { return query2(x, y, 1, 0, n); }

int broken = 0;

void fix(int r)
{
    long long delta = query1_(r-1) - query1_(r);
    if (delta <= 0)
        return;
    long long ii = (delta + d - 1) / d;
    if (query1_(dominoes[top]) < d * ii)
    {
        int lower = dominoes[top], upper = r;
        while (upper - lower > 1)
        {
            int mid = lower + (upper - lower) / 2;
            if (query1_(mid) < d * ii) lower = mid;
            else upper = mid;
        }
        if (lower > broken)
        {
            broken = lower;
            add_(broken, broken, -1e18, 0);
            dominoes[top=1]=broken+1;
        }
    }
    add_(dominoes[top], r-1, -ii * d, ii);
}

int main()
{
    scanf("%d%lld",&n,&d);
    add_(0, 0, -1e18, 0);
    for(int i=1;i<=n;++i)scanf("%lld",&c), add_(i, i, c, 0);

    scanf("%d",&q);
    for(int ll,rr,i=0;i<q;++i)scanf("%d%d",&ll,&rr),push(rr,i),push(rr,ll);

    for(int r=1;r<=n;++r)
    {
        fix(r);

        while (top && query1_(dominoes[top]) - query1_(dominoes[top]-1) < d)
            fix(dominoes[top--]);

        if (query1_(r) - query1_(r-1) >= d)
            dominoes[++top] = r;

        for(int j=0;j<eo[r];j+=2)
        {
            int ll=eh[r][j+1], ii=eh[r][j];
            if (broken >= ll)
                ans[ii] = -1;
            else
                ans[ii] = query2_(ll, r);
        }
    }

    for(int i=0;i<q;++i)printf("%lld\n",ans[i]);
}

Compilation message

Main.c: In function 'push':
Main.c:15:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |     else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
Main.c: In function 'main':
Main.c:109:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d%lld",&n,&d);
      |     ^~~~~~~~~~~~~~~~~~~~~
Main.c:111:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     for(int i=1;i<=n;++i)scanf("%lld",&c), add_(i, i, c, 0);
      |                          ^~~~~~~~~~~~~~~~
Main.c:113:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d",&q);
      |     ^~~~~~~~~~~~~~
Main.c:114:31: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     for(int ll,rr,i=0;i<q;++i)scanf("%d%d",&ll,&rr),push(rr,i),push(rr,ll);
      |                               ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 5 ms 10824 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10812 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 4 ms 10844 KB Output is correct
9 Correct 4 ms 10840 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 40736 KB Output is correct
2 Correct 372 ms 36948 KB Output is correct
3 Correct 70 ms 15508 KB Output is correct
4 Correct 335 ms 41300 KB Output is correct
5 Correct 336 ms 41044 KB Output is correct
6 Correct 327 ms 40800 KB Output is correct
7 Correct 315 ms 40804 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 19484 KB Output is correct
2 Correct 520 ms 45136 KB Output is correct
3 Correct 509 ms 45156 KB Output is correct
4 Correct 514 ms 45152 KB Output is correct
5 Correct 511 ms 45652 KB Output is correct
6 Correct 472 ms 41764 KB Output is correct
7 Correct 470 ms 41808 KB Output is correct
8 Correct 486 ms 42008 KB Output is correct
9 Correct 476 ms 41816 KB Output is correct
10 Correct 388 ms 37752 KB Output is correct
11 Correct 428 ms 37900 KB Output is correct
12 Correct 473 ms 42012 KB Output is correct
13 Correct 446 ms 41884 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 31060 KB Output is correct
2 Correct 399 ms 37916 KB Output is correct
3 Correct 200 ms 25552 KB Output is correct
4 Correct 456 ms 37972 KB Output is correct
5 Correct 494 ms 44328 KB Output is correct
6 Correct 562 ms 45268 KB Output is correct
7 Correct 432 ms 35840 KB Output is correct
8 Correct 528 ms 44856 KB Output is correct
9 Correct 333 ms 37380 KB Output is correct
10 Correct 269 ms 41088 KB Output is correct
11 Correct 394 ms 45584 KB Output is correct
12 Correct 325 ms 45140 KB Output is correct
13 Correct 537 ms 52768 KB Output is correct
14 Correct 434 ms 44368 KB Output is correct
15 Correct 525 ms 52480 KB Output is correct
16 Correct 436 ms 44904 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 5 ms 10824 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10812 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 4 ms 10844 KB Output is correct
9 Correct 4 ms 10840 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 411 ms 40736 KB Output is correct
15 Correct 372 ms 36948 KB Output is correct
16 Correct 70 ms 15508 KB Output is correct
17 Correct 335 ms 41300 KB Output is correct
18 Correct 336 ms 41044 KB Output is correct
19 Correct 327 ms 40800 KB Output is correct
20 Correct 315 ms 40804 KB Output is correct
21 Correct 115 ms 19484 KB Output is correct
22 Correct 520 ms 45136 KB Output is correct
23 Correct 509 ms 45156 KB Output is correct
24 Correct 514 ms 45152 KB Output is correct
25 Correct 511 ms 45652 KB Output is correct
26 Correct 472 ms 41764 KB Output is correct
27 Correct 470 ms 41808 KB Output is correct
28 Correct 486 ms 42008 KB Output is correct
29 Correct 476 ms 41816 KB Output is correct
30 Correct 388 ms 37752 KB Output is correct
31 Correct 428 ms 37900 KB Output is correct
32 Correct 473 ms 42012 KB Output is correct
33 Correct 446 ms 41884 KB Output is correct
34 Correct 371 ms 31060 KB Output is correct
35 Correct 399 ms 37916 KB Output is correct
36 Correct 200 ms 25552 KB Output is correct
37 Correct 456 ms 37972 KB Output is correct
38 Correct 494 ms 44328 KB Output is correct
39 Correct 562 ms 45268 KB Output is correct
40 Correct 432 ms 35840 KB Output is correct
41 Correct 528 ms 44856 KB Output is correct
42 Correct 333 ms 37380 KB Output is correct
43 Correct 269 ms 41088 KB Output is correct
44 Correct 394 ms 45584 KB Output is correct
45 Correct 325 ms 45140 KB Output is correct
46 Correct 537 ms 52768 KB Output is correct
47 Correct 434 ms 44368 KB Output is correct
48 Correct 525 ms 52480 KB Output is correct
49 Correct 436 ms 44904 KB Output is correct
50 Correct 517 ms 52820 KB Output is correct
51 Correct 470 ms 46376 KB Output is correct
52 Correct 501 ms 49540 KB Output is correct
53 Correct 417 ms 45276 KB Output is correct
54 Correct 449 ms 49616 KB Output is correct
55 Correct 524 ms 52736 KB Output is correct
56 Correct 366 ms 46388 KB Output is correct
57 Correct 357 ms 44092 KB Output is correct
58 Correct 348 ms 41296 KB Output is correct
59 Correct 471 ms 50748 KB Output is correct
60 Correct 424 ms 48196 KB Output is correct
61 Correct 395 ms 45228 KB Output is correct
62 Correct 375 ms 44028 KB Output is correct
63 Correct 442 ms 49488 KB Output is correct
64 Correct 409 ms 47248 KB Output is correct