Submission #126312

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
126312	2019-07-07 11:37:50	TadijaSebez	Cake 3 (JOI19_cake3)	C++11	100 / 100	3405 ms	89220 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll inf=1e18;
const int N=200050;
const int M=20*N;
int v[N],c[N],id[N],idv[N],pos[N],n,m;
int ls[M],rs[M],tsz,root[N],sz[M];
ll sum[M];
void Set(int p, int &c, int ss, int se, int qi, ll x)
{
  c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+x;sz[c]=sz[p]+1;
  if(ss==se) return;
  int mid=ss+se>>1;
  if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,x);
  else Set(rs[p],rs[c],mid+1,se,qi,x);
}
ll Get(int p, int c, int ss, int se, int k)
{
  ll ans=0;
  while(1)
  {
    if(ss==se){ if(k>0) ans+=sum[c];break;}
    int mid=ss+se>>1;
    int A=sz[ls[c]]-sz[ls[p]];
    if(A<=k) k-=A,ans+=sum[ls[c]]-sum[ls[p]],ss=mid+1,p=rs[p],c=rs[c];
    else se=mid,p=ls[p],c=ls[c];
  }
  return ans;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

cake3.cpp: In function 'void Set(int, int&, int, int, int, long long int)':
cake3.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'long long int Get(int, int, int, int, int)':
cake3.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<R.size();i++)
                  ~^~~~~~~~~
cake3.cpp:68:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<L.size() && R[i]-L[j]+1>=m)
         ~^~~~~~~~~
cake3.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake3.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:56:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76