Submission #387221

# Submission time Handle Problem Language Result Execution time Memory
387221 2021-04-08T06:49:36 Z uacoder123 Snowball (JOI21_ho_t2) C++14
0 / 100
12 ms 10092 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
lli n,q;
lli a[200100],pos[200100];
vi sum(200100),po1(200100),ne1(200100);
vi v;
lli ans[200100];
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>q;
  for(lli i=0;i<n;++i)
    cin>>pos[i];
  for(lli i=0;i<q;++i)
  {
    cin>>a[i];
    if(i!=0)
      a[i]=a[i]+a[i-1];
  }
  lli po=0,ne=0;
  for(lli i=0;i<q;++i)
  {
    if(a[i]>0&&a[i]>po)
    {
      v.pb(a[i]-po);
      po=a[i];
    }
    else if(a[i]<0&&a[i]<ne)
    {
      v.pb(a[i]-ne);
      ne=a[i];
    }
  }
  lli n1=v.size();
  for(lli i=0;i<n1;++i)
  {
    sum[i+1]=abs(v[i]);
    if(v[i]>0)
      po1[i+1]=v[i];
    else
      ne1[i+1]=v[i];
    if(i>0)
    {
      sum[i+1]+=sum[i];
      po1[i+1]+=po1[i];
      ne1[i+1]+=ne1[i];
    }
  }
  for(lli i=1;i<n;++i)
  {
    lli l=pos[i]-pos[i-1];
    lli it=lower_bound(sum.begin()+1,sum.begin()+v.size()+1,l)-sum.begin();
    if(it==v.size()+1)
      it--;
    ans[i-1]+=po1[it];
    ans[i]+=-ne1[it];
    if(v[it-1]>0)
      ans[i-1]-=max(0*1LL,(v[it-1]-(l-sum[it-1])));
    else
      ans[i]-=max(0*1LL,(-v[it-1]-(l-sum[it-1])));
  }
  ans[0]+=-ne1[n1];
  ans[n-1]+=po1[n1];
  for(lli i=0;i<n;++i)
    cout<<ans[i]<<endl;
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:10: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     if(it==v.size()+1)
      |        ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 9 ms 5100 KB Output is correct
5 Correct 9 ms 5100 KB Output is correct
6 Correct 9 ms 5100 KB Output is correct
7 Correct 11 ms 5100 KB Output is correct
8 Correct 9 ms 5228 KB Output is correct
9 Correct 9 ms 5100 KB Output is correct
10 Correct 8 ms 5100 KB Output is correct
11 Correct 8 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 9 ms 5100 KB Output is correct
16 Correct 9 ms 5116 KB Output is correct
17 Correct 9 ms 5100 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Runtime error 12 ms 10092 KB Execution killed with signal 11
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 9 ms 5100 KB Output is correct
5 Correct 9 ms 5100 KB Output is correct
6 Correct 9 ms 5100 KB Output is correct
7 Correct 11 ms 5100 KB Output is correct
8 Correct 9 ms 5228 KB Output is correct
9 Correct 9 ms 5100 KB Output is correct
10 Correct 8 ms 5100 KB Output is correct
11 Correct 8 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 9 ms 5100 KB Output is correct
16 Correct 9 ms 5116 KB Output is correct
17 Correct 9 ms 5100 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Runtime error 12 ms 10092 KB Execution killed with signal 11