Submission #262359

#	Time	Username	Problem	Language	Result	Execution time	Memory
262359		uacoder123	Horses (IOI15_horses)	C++14	17 / 100	252 ms	44356 KiB

horses

        #include "horses.h"
        #include <bits/stdc++.h>
        using namespace std;
        #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 <lli,ii> iii;
        typedef vector <lli> vi;
         
        lli segt[2000001],lazy[2000001],arr1[500001],arr2[500001];
        lli n,mod=1000000007;
        lli p(lli a)
        {
          lli b=0,ans=1;
          while((1LL<<b)<=mod-2)
          {
            if(bit(mod-2,b))
              ans=(ans*a)%mod;
            a=(a*a)%mod;
            b++;
          }
          return ans;
        }
        void up(lli node,lli l,lli r,lli s,lli e,lli v)
        {
          if(l>e||r<s)
            return;
          if(lazy[node]!=1)
          {
            segt[node]=(segt[node]*lazy[node])%mod;
            if(l!=r)
            {
              lazy[2*node+1]=(lazy[2*node+1]*lazy[node])%mod;
              lazy[2*node+2]=(lazy[2*node+2]*lazy[node])%mod;
            }
            lazy[node]=1;
          }
          if(l>=s&&r<=e)
          {
            segt[node]=(segt[node]*v)%mod;
            if(l!=r)
            {
              lazy[2*node+1]=(lazy[2*node+1]*v)%mod;
              lazy[2*node+2]=(lazy[2*node+2]*v)%mod;
            }
            return;
          }
          lli m=(l+r)/2;
          up(2*node+1,l,m,s,e,v);
          up(2*node+2,m+1,r,s,e,v);
          segt[node]=max(segt[2*node+1],segt[2*node+2]);
        }
        int init(int N, int X[], int Y[]) 
        {
          for(lli i=0;i<=2000001;++i)
          {
            segt[i]=1;
            lazy[i]=1;
          }
          n=N;
          lli cur=(1);
          for(lli i=0;i<n;++i)
          {
            arr1[i]=X[i];
            arr2[i]=Y[i];
            cur=(cur*X[i])%mod;
            up(0,0,n-1,i,i,(cur*Y[i])%mod);
          }
          return segt[0];
        }
         
        int updateX(int pos, int val) 
        {
          lli v=p(arr1[pos]);
          v=(v*val)%mod;
          arr1[pos]=val;
          up(0,0,n-1,pos,n-1,v);
          return segt[0];
        }
        int updateY(int pos, int val) 
        {
          lli v=p(arr2[pos]);
          v=(v*val)%mod;
          arr2[pos]=val;
          up(0,0,n-1,pos,pos,v);
          return segt[0];
        }

Compilation message (stderr)

horses.cpp: In function 'lli p(lli)':
horses.cpp:26:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   26 |             if(bit(mod-2,b))
      |                    ~~~^~
horses.cpp:12:27: note: in definition of macro 'bit'
   12 |         #define bit(x,b) (x&(1LL<<b))
      |                           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:24: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 |           return segt[0];
      |                  ~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:87:24: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
   87 |           return segt[0];
      |                  ~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:24: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |           return segt[0];
      |                  ~~~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:66:20: warning: iteration 2000001 invokes undefined behavior [-Waggressive-loop-optimizations]
   66 |             segt[i]=1;
      |             ~~~~~~~^~
horses.cpp:64:24: note: within this loop
   64 |           for(lli i=0;i<=2000001;++i)
      |                       ~^~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23