Submission #1052983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052983		modwwe	Horses (IOI15_horses)	C++17	100 / 100	211 ms	68180 KiB

horses

//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int2 long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const ll inf=1e18;
const int2 mod2=1e9+7;
const int2  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    ll a;
    ll b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
int2  i,s10,s12;
int2 kk;
int2 el=29;

set<int2> s;
int2 a[500001];
int2 b[500001];
struct IT
{    int2 t[2000001];

     void build(int node,int l,int r)
      {
           if(l==r){t[node]=a[l]; return;}
           int mid=l+r>>1;
            build(node<<1,l,mid);
            build(node<<1|1,mid+1,r);
             t[node]=(t[node<<1]*t[node<<1|1])%mod2;
      }
      void upd(int node,int l,int r,int l1)
      {
           if(l==r){t[node]=a[l]; return;}
           int mid=l+r>>1;
            if(l1<=mid)upd(node<<1,l,mid,l1);
             else upd(node<<1|1,mid+1,r,l1);
              t[node]=(t[node<<1]*t[node<<1|1])%mod2;
      }
      int2 get(int node,int l,int r,int l1,int r1)
        {
             if(l>r1||r<l1) return 1;
             if(l>=l1&&r<=r1) return t[node];
              int mid=l+r>>1;
               return get(node<<1,l,mid,l1,r1)*get(node<<1|1,mid+1,r,l1,r1)%mod2;
        }
}st;
struct IT2{
    int2 t[2000001];
void build(int node,int l,int r)
      {
           if(l==r){t[node]=b[l]; return;}
           int mid=l+r>>1;
            build(node<<1,l,mid);
            build(node<<1|1,mid+1,r);
             t[node]=max(t[node<<1],t[node<<1|1]);
      }
      void upd(int node,int l,int r,int l1)
      {
           if(l==r){t[node]=b[l]; return;}
           int mid=l+r>>1;
            if(l1<=mid)upd(node<<1,l,mid,l1);
             else upd(node<<1|1,mid+1,r,l1);
             t[node]=max(t[node<<1],t[node<<1|1]);
      }
      int2 get(int node,int l,int r,int l1,int r1)
        {
             if(l>r1||r<l1) return 1;
             if(l>=l1&&r<=r1) return t[node];
              int mid=l+r>>1;
               return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
        }
}st2;
void setup()
 {
      for(int i=n;i>=1;--i)
         if(a[i]!=1)
          s.insert(i);
          s.insert(1);
        auto x=s.end();
        x--;
        s2=0;
        s5=n;
        while(1)
        {
            s6=st2.get(1,1,n,*x,s5);
            if(s6>s2) s3=*x,s2=s6,s8=s6;
         s2=s2*a[*x];
         s5=*x-1;
         if(x==s.begin()) break;
x--;
          if(s2>1e9) break;
        }
 }
 void setup2()
 {
       auto x=s.end();
                 s.insert(1);
        x--;
        s2=0;
        s5=n;
        s3=0;
        s8=0;
        while(1)
        {
            s6=st2.get(1,1,n,*x,s5);
            if(s6>s2) s3=*x,s2=s6,s8=s6;
         s2=s2*a[*x];
         s5=*x-1;
         if(x==s.begin()) break;
x--;
          if(s2>1e9) break;
        }
 }
int init(int N,int X[],int Y[])
{
n=N;
   for(int i=1;i<=n;i++)
    a[i]=X[i-1];
    for(int i=1;i<=n;i++)
         b[i]=Y[i-1];
     st.build(1,1,n);
     st2.build(1,1,n);
     setup();
s3=s8*st.get(1,1,n,1,s3)%mod2;
 return s3;
}
int updateY(int pos, int val)
{
    l=pos;
    r=val;
      l++;
    b[l]=r;
    st2.upd(1,1,n,l);
    setup2();
    s3=(s8*st.get(1,1,n,1,s3))%mod2;
 return s3;
}
int updateX(int pos, int val)
{
    l=pos;
    r=val;
     l++;
         if(a[l]!=1&&r==1) s.erase(l);
          if(a[l]==1&&r!=1) s.insert(l);
          a[l]=r;
           st.upd(1,1,n,l);
           setup2();
           s3=(s8*st.get(1,1,n,1,s3))%mod2;
 return s3;
}

Compilation message (stderr)

horses.cpp: In member function 'void IT::build(int, int, int)':
horses.cpp:57:36: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   57 |      void build(int node,int l,int r)
      |                                ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:57:30: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   57 |      void build(int node,int l,int r)
      |                          ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:60:16: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
   60 |            int mid=l+r>>1;
      |                ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |            int mid=l+r>>1;
      |                    ~^~
horses.cpp: In member function 'void IT::upd(int, int, int, int)':
horses.cpp:65:35: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   65 |       void upd(int node,int l,int r,int l1)
      |                               ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:65:29: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   65 |       void upd(int node,int l,int r,int l1)
      |                         ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:68:16: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
   68 |            int mid=l+r>>1;
      |                ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |            int mid=l+r>>1;
      |                    ~^~
horses.cpp: In member function 'long long int IT::get(int, int, int, int, int)':
horses.cpp:73:35: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   73 |       int2 get(int node,int l,int r,int l1,int r1)
      |                               ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:73:29: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   73 |       int2 get(int node,int l,int r,int l1,int r1)
      |                         ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:77:19: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
   77 |               int mid=l+r>>1;
      |                   ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:77:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |               int mid=l+r>>1;
      |                       ~^~
horses.cpp: In member function 'void IT2::build(int, int, int)':
horses.cpp:83:31: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   83 | void build(int node,int l,int r)
      |                           ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:83:25: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   83 | void build(int node,int l,int r)
      |                     ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:86:16: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
   86 |            int mid=l+r>>1;
      |                ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |            int mid=l+r>>1;
      |                    ~^~
horses.cpp: In member function 'void IT2::upd(int, int, int, int)':
horses.cpp:91:35: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   91 |       void upd(int node,int l,int r,int l1)
      |                               ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:91:29: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   91 |       void upd(int node,int l,int r,int l1)
      |                         ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:94:16: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
   94 |            int mid=l+r>>1;
      |                ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |            int mid=l+r>>1;
      |                    ~^~
horses.cpp: In member function 'long long int IT2::get(int, int, int, int, int)':
horses.cpp:99:35: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   99 |       int2 get(int node,int l,int r,int l1,int r1)
      |                               ~~~~^
horses.cpp:46:77: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                             ^
horses.cpp:99:29: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   99 |       int2 get(int node,int l,int r,int l1,int r1)
      |                         ~~~~^
horses.cpp:46:75: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                           ^
horses.cpp:103:19: warning: declaration of 'mid' shadows a global declaration [-Wshadow]
  103 |               int mid=l+r>>1;
      |                   ^~~
horses.cpp:46:79: note: shadowed declaration is here
   46 | int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
      |                                                                               ^~~
horses.cpp:103:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |               int mid=l+r>>1;
      |                       ~^~
horses.cpp: In function 'void setup()':
horses.cpp:109:15: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  109 |       for(int i=n;i>=1;--i)
      |               ^
horses.cpp:47:7: note: shadowed declaration is here
   47 | int2  i,s10,s12;
      |       ^
horses.cpp:109:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |       for(int i=n;i>=1;--i)
      |                 ^
horses.cpp:110:10: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  110 |          if(a[i]!=1)
      |          ^~
horses.cpp:112:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  112 |           s.insert(1);
      |           ^
horses.cpp:119:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |             s6=st2.get(1,1,n,*x,s5);
      |                            ^
horses.cpp:119:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |             s6=st2.get(1,1,n,*x,s5);
      |                              ^~
horses.cpp:119:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |             s6=st2.get(1,1,n,*x,s5);
      |                                 ^~
horses.cpp:125:14: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  125 |           if(s2>1e9) break;
      |              ^~
horses.cpp: In function 'void setup2()':
horses.cpp:139:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |             s6=st2.get(1,1,n,*x,s5);
      |                            ^
horses.cpp:139:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |             s6=st2.get(1,1,n,*x,s5);
      |                              ^~
horses.cpp:139:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |             s6=st2.get(1,1,n,*x,s5);
      |                                 ^~
horses.cpp:145:14: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  145 |           if(s2>1e9) break;
      |              ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:151:12: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  151 |    for(int i=1;i<=n;i++)
      |            ^
horses.cpp:47:7: note: shadowed declaration is here
   47 | int2  i,s10,s12;
      |       ^
horses.cpp:151:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  151 |    for(int i=1;i<=n;i++)
      |    ^~~
horses.cpp:153:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  153 |     for(int i=1;i<=n;i++)
      |     ^~~
horses.cpp:153:13: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  153 |     for(int i=1;i<=n;i++)
      |             ^
horses.cpp:47:7: note: shadowed declaration is here
   47 | int2  i,s10,s12;
      |       ^
horses.cpp:155:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  155 |      st.build(1,1,n);
      |                   ^
horses.cpp:156:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |      st2.build(1,1,n);
      |                    ^
horses.cpp:158:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 | s3=s8*st.get(1,1,n,1,s3)%mod2;
      |                  ^
horses.cpp:158:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 | s3=s8*st.get(1,1,n,1,s3)%mod2;
      |                      ^~
horses.cpp:159:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  159 |  return s3;
      |         ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:167:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  167 |     st2.upd(1,1,n,l);
      |                 ^
horses.cpp:167:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  167 |     st2.upd(1,1,n,l);
      |                   ^
horses.cpp:169:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  169 |     s3=(s8*st.get(1,1,n,1,s3))%mod2;
      |                       ^
horses.cpp:169:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  169 |     s3=(s8*st.get(1,1,n,1,s3))%mod2;
      |                           ^~
horses.cpp:170:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  170 |  return s3;
      |         ^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:180:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |            st.upd(1,1,n,l);
      |                       ^
horses.cpp:180:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |            st.upd(1,1,n,l);
      |                         ^
horses.cpp:182:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  182 |            s3=(s8*st.get(1,1,n,1,s3))%mod2;
      |                              ^
horses.cpp:182:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  182 |            s3=(s8*st.get(1,1,n,1,s3))%mod2;
      |                                  ^~
horses.cpp:183:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  183 |  return s3;
      |         ^~

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