Submission #3990786


Source Code Expand

Copy
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000000000000LL
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll n,q,x,a[MAXN],sum[MAXN],even[MAXN];
int main()
{
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    a[0]=-INF;
    for(ll i=1;i<=n;i++) 
    {
        sum[i]=sum[i-1]+a[i];
        even[i]=even[i-1]+a[i]*(i&1?0:1);
    }
    for(ll i=0;i<q;i++)
    {
        scanf("%lld",&x);
        if(x>=a[n]) 
        {
            if(n&1) printf("%lld\n",sum[n]-even[n]);
            else printf("%lld\n",even[n]);
            continue;
        }
        ll pos=lower_bound(a+1,a+n+1,x)-a;
        ll l=pos-1,r=n;
        while(r-l>1)
        {
            ll mid=(l+r)/2;
            ll numr=n-mid+1;
            ll numl=mid-(lower_bound(a,a+n+1,2*x-a[mid])-a);
            if(numr-numl<=1) r=mid; else l=mid;  
        }
        ll ans=sum[n]-sum[r-1];
        ll pp=n-2*(n-r+1);
        if(pp&1) ans+=sum[pp]-even[pp]; else ans+=even[pp];
        printf("%lld\n",ans);
    }
    return 0;
}

Submission Info

Submission Time
Task D - Nearest Card Game
User Roundgod
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1188 Byte
Status
Exec Time 184 ms
Memory 4096 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&q);
                            ^
./Main.cpp:15:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
                                             ^
./Main.cpp:24:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
                         ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01.txt 3 ms 384 KB
02.txt 3 ms 384 KB
03.txt 3 ms 384 KB
04.txt 2 ms 384 KB
05.txt 3 ms 384 KB
06.txt 2 ms 256 KB
07.txt 26 ms 1280 KB
08.txt 170 ms 4096 KB
09.txt 80 ms 1536 KB
10.txt 80 ms 1536 KB
11.txt 184 ms 4096 KB
12.txt 183 ms 4096 KB
13.txt 77 ms 4096 KB
14.txt 115 ms 4096 KB
15.txt 103 ms 4096 KB
16.txt 65 ms 4096 KB
17.txt 170 ms 4096 KB
18.txt 87 ms 4096 KB
19.txt 158 ms 4096 KB
20.txt 164 ms 3712 KB
21.txt 164 ms 3712 KB
22.txt 130 ms 4096 KB
23.txt 127 ms 4096 KB
24.txt 119 ms 4096 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB