oj.uz

Submission #501142

# Submission time Handle Problem Language Result Execution time Memory
501142 2022-01-02T13:05:02 Z shahriarkhan Snowball (JOI21_ho_t2) C++14
100 / 100
 1872 ms 13760 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 2e5 + 5 ;

const long long INF = 1e18 + 5 ;

long long pref_mx[MX] , pref_mn[MX] ;

int n , q ;

int smaller_equal(long long val)
{
    if(pref_mn[q]>val) return (q+1) ;
    int low = 0 , high = q ;
    while(low<high)
    {
        int mid = (low+high)>>1 ;
        if(pref_mn[mid]<=val) high = mid ;
        else low = mid + 1 ;
    }
    return low ;
}

int bigger_equal(long long val)
{
    if(pref_mx[q]<val) return (q+1) ;
    int low = 0 , high = q ;
    while(low<high)
    {
        int mid = (low+high)>>1 ;
        if(pref_mx[mid]>=val) high = mid ;
        else low = mid + 1 ;
    }
    return low ;
}

int main()
{
    scanf("%d%d",&n,&q) ;
    long long x[n+2] , sum = 0 , ans[n+1] = {0} ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%lld",&x[i]) ;
    }
    pref_mx[0] = 0 , pref_mn[0] = INF ;
    for(int i = 1 ; i <= q ; ++i)
    {
        long long cur ;
        scanf("%lld",&cur) ;
        sum += cur ;
        pref_mx[i] = max(pref_mx[i-1],sum) ;
        pref_mn[i] = min(pref_mn[i-1],sum) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        long long low = 0 , high = INF , left = 0 , right = 0 ;
        while(low<high)
        {
            long long mid = (low+high+1)>>1 ;
            if(i==n)
            {
                int pos = bigger_equal(mid) ;
                if(pos>q) high = mid - 1 ;
                else low = mid ;
            }
            else
            {
                if((x[i]+mid)>x[i+1]) high = mid - 1 ;
                else if(bigger_equal(mid)<smaller_equal(x[i]-x[i+1]+mid-1)) low = mid ;
                else high = mid - 1 ;
            }
        }
        left = low ;
        low = 0 , high = INF ;
        while(low<high)
        {
            long long mid = (low+high+1)>>1 ;
            if(i==1)
            {
                int pos = smaller_equal(-mid) ;
                if(pos>q) high = mid - 1 ;
                else low = mid ;
            }
            else
            {
                if((x[i]-mid)<x[i-1]) high = mid - 1 ;
                else if(smaller_equal(-mid)<bigger_equal(x[i]-x[i-1]-mid+1)) low = mid ;
                else high = mid - 1 ;
            }
        }
        right = low ;
        ans[i] = left+right ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        printf("%lld\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld",&x[i]) ;
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld",&cur) ;
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 11 ms 360 KB Output is correct
5 Correct 11 ms 460 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 8 ms 364 KB Output is correct
8 Correct 7 ms 360 KB Output is correct
9 Correct 6 ms 360 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 13 ms 404 KB Output is correct
16 Correct 10 ms 332 KB Output is correct
17 Correct 7 ms 304 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 1 ms 332 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 11 ms 360 KB Output is correct
5 Correct 11 ms 460 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 8 ms 364 KB Output is correct
8 Correct 7 ms 360 KB Output is correct
9 Correct 6 ms 360 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 13 ms 404 KB Output is correct
16 Correct 10 ms 332 KB Output is correct
17 Correct 7 ms 304 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 37 ms 5656 KB Output is correct
21 Correct 34 ms 5276 KB Output is correct
22 Correct 34 ms 5040 KB Output is correct
23 Correct 46 ms 4932 KB Output is correct
24 Correct 222 ms 5456 KB Output is correct
25 Correct 1872 ms 11808 KB Output is correct
26 Correct 1825 ms 11740 KB Output is correct
27 Correct 1781 ms 11336 KB Output is correct
28 Correct 1692 ms 11508 KB Output is correct
29 Correct 1510 ms 11068 KB Output is correct
30 Correct 933 ms 10480 KB Output is correct
31 Correct 164 ms 9920 KB Output is correct
32 Correct 133 ms 10016 KB Output is correct
33 Correct 139 ms 1456 KB Output is correct
34 Correct 1745 ms 12148 KB Output is correct
35 Correct 1661 ms 11504 KB Output is correct
36 Correct 1847 ms 11796 KB Output is correct
37 Correct 1762 ms 11556 KB Output is correct
38 Correct 1684 ms 11460 KB Output is correct
39 Correct 1795 ms 11588 KB Output is correct
40 Correct 1149 ms 11524 KB Output is correct
41 Correct 41 ms 6076 KB Output is correct
42 Correct 111 ms 9976 KB Output is correct
43 Correct 352 ms 13256 KB Output is correct
44 Correct 32 ms 5932 KB Output is correct
45 Correct 329 ms 11600 KB Output is correct
46 Correct 484 ms 13504 KB Output is correct
47 Correct 348 ms 13636 KB Output is correct
48 Correct 251 ms 13760 KB Output is correct