oj.uz

Submission #978486

# Submission time Handle Problem Language Result Execution time Memory
978486 2024-05-09T09:00:20 Z sleepntsheep Fish 3 (JOI24_fish3) C
28 / 100
 553 ms 52884 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)
{
    if(y<a||b<x)return 0;
    return 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 >= dominoes[top])
                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:112:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d%lld",&n,&d);
      |     ^~~~~~~~~~~~~~~~~~~~~
Main.c:114:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     for(int i=1;i<=n;++i)scanf("%lld",&c), add_(i, i, c, 0);
      |                          ^~~~~~~~~~~~~~~~
Main.c:116:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     scanf("%d",&q);
      |     ^~~~~~~~~~~~~~
Main.c:117:31: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     for(int ll,rr,i=0;i<q;++i)scanf("%d%d",&ll,&rr),push(rr,i),push(rr,ll);
      |                               ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10596 KB Output is correct
4 Correct 6 ms 10840 KB Output is correct
5 Incorrect 7 ms 10892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 40928 KB Output is correct
2 Correct 393 ms 36916 KB Output is correct
3 Incorrect 114 ms 15172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 19328 KB Output is correct
2 Correct 512 ms 52872 KB Output is correct
3 Correct 540 ms 52884 KB Output is correct
4 Correct 517 ms 52708 KB Output is correct
5 Correct 530 ms 52808 KB Output is correct
6 Correct 515 ms 46408 KB Output is correct
7 Correct 513 ms 46148 KB Output is correct
8 Correct 487 ms 49416 KB Output is correct
9 Correct 494 ms 49644 KB Output is correct
10 Correct 419 ms 45152 KB Output is correct
11 Correct 390 ms 45100 KB Output is correct
12 Correct 481 ms 49964 KB Output is correct
13 Correct 474 ms 49660 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 30956 KB Output is correct
2 Correct 370 ms 37972 KB Output is correct
3 Correct 223 ms 25532 KB Output is correct
4 Correct 392 ms 37932 KB Output is correct
5 Correct 553 ms 44392 KB Output is correct
6 Correct 551 ms 45732 KB Output is correct
7 Correct 432 ms 36180 KB Output is correct
8 Correct 534 ms 44884 KB Output is correct
9 Incorrect 379 ms 37836 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10596 KB Output is correct
4 Correct 6 ms 10840 KB Output is correct
5 Incorrect 7 ms 10892 KB Output isn't correct
6 Halted 0 ms 0 KB -