Submission #69165

#	Time	Username	Problem	Language	Result	Execution time	Memory
69165		yusufake	Horses (IOI15_horses)	C++98	100 / 100	995 ms	205268 KiB

horses

#include<bits/stdc++.h>
using namespace std;
#include "horses.h"

#define _   int v, int tl, int tr, int l, int r
#define tm  (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
#define ll long long

const ll mod = 1e9 + 7;
const ll N = 5e5 + 5;
set < int > S;
set < int > :: iterator it;
ll s[N*4],ss[N<<2],X[N],Y[N];

ll up(_, ll x){
    if(tl > r || tr < l) return s[v];
    if(tl == tr) return s[v]=x;
    return s[v] = max(up(sol,x) , up(sag,x));
}
ll qry(_){
    if(tl > r || tr < l) return 0;
    if(tl >= l && tr <= r) return s[v];
    return max(qry(sol) , qry(sag));
}
ll up2(_, ll x){
    if(tl > r || tr < l) return ss[v];
    if(tl == tr) return ss[v]=x;
    return ss[v] = up2(sol,x) * up2(sag,x) % mod;
}
ll qry2(_){
    if(tl > r || tr < l) return 1;
    if(tl >= l && tr <= r) return ss[v];
    return qry2(sol) * qry2(sag) % mod;
}

ll A[77],B[77],l,r,j,n,t,mx;
ll f(){
    r = n-1;
    j = 0;
    t = 1;
    mx = 0;
    for(it = S.end(); it!=S.begin();){
        it--;
        l = *it;
        j++;
        B[j] = qry(1,0,n-1,l,r);
        A[j] = X[l];
        r = l-1;
        t *= X[l];
        if(t >= mod) break;
    }
    if(r > -1 && t < mod){
        l = 0;
        j++;
        B[j] = qry(1,0,n-1,l,r);
        A[j] = X[l];
        r = l-1;
    }
    A[j] = A[j+1] = 1;
    for(; j ; j--){
        A[j] *= A[j+1];
        mx = max(mx , A[j]*B[j]);
    }
    //cout << mx << " ss\n"; 
    return mx%mod*qry2(1,0,n-1,0,r+1)%mod;
}

int updateX(int pos, int val) {
    if(X[pos] == 1 && val > 1) S.insert(pos);
    if(X[pos] > 1 && val == 1) S.erase(pos);
    X[pos] = val;
    up2(1,0,n-1,pos,pos,val);
    return f();
}
int updateY(int pos, int val) {
    Y[pos] = val;
    up(1,0,n-1,pos,pos,val);
    return f();
}
int init(int a, int x[], int y[]){
    int i;
    n = a;
    for(i=0;i<n;i++){
        if(x[i] > 1)
            S.insert(i);
        X[i] = x[i];
        up2(1,0,n-1,i,i,X[i]);
    }
    for(i=0;i<n;i++){
        Y[i] = y[i];
        up(1,0,n-1,i,i,Y[i]);
    }
    return f();
}

Compilation message (stderr)

horses.cpp: In function 'long long int up(int, int, int, int, int, long long int)':
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
horses.cpp:20:26: note: in expansion of macro 'sol'
     return s[v] = max(up(sol,x) , up(sag,x));
                          ^~~
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
horses.cpp:20:38: note: in expansion of macro 'sag'
     return s[v] = max(up(sol,x) , up(sag,x));
                                      ^~~
horses.cpp: In function 'long long int qry(int, int, int, int, int)':
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
horses.cpp:25:20: note: in expansion of macro 'sol'
     return max(qry(sol) , qry(sag));
                    ^~~
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
horses.cpp:25:31: note: in expansion of macro 'sag'
     return max(qry(sol) , qry(sag));
                               ^~~
horses.cpp: In function 'long long int up2(int, int, int, int, int, long long int)':
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
horses.cpp:30:24: note: in expansion of macro 'sol'
     return ss[v] = up2(sol,x) * up2(sag,x) % mod;
                        ^~~
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
horses.cpp:30:37: note: in expansion of macro 'sag'
     return ss[v] = up2(sol,x) * up2(sag,x) % mod;
                                     ^~~
horses.cpp: In function 'long long int qry2(int, int, int, int, int)':
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:7:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
horses.cpp:35:17: note: in expansion of macro 'sol'
     return qry2(sol) * qry2(sag) % mod;
                 ^~~
horses.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
horses.cpp:8:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
horses.cpp:35:29: note: in expansion of macro 'sag'
     return qry2(sol) * qry2(sag) % mod;
                             ^~~
horses.cpp: In function 'long long int f()':
horses.cpp:48:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         B[j] = qry(1,0,n-1,l,r);
                        ~^~
horses.cpp:48:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         B[j] = qry(1,0,n-1,l,r);
                               ^
horses.cpp:48:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:57:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         B[j] = qry(1,0,n-1,l,r);
                        ~^~
horses.cpp:57:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         B[j] = qry(1,0,n-1,l,r);
                               ^
horses.cpp:57:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:67:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return mx%mod*qry2(1,0,n-1,0,r+1)%mod;
                            ~^~
horses.cpp:67:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return mx%mod*qry2(1,0,n-1,0,r+1)%mod;
                                  ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:74:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     up2(1,0,n-1,pos,pos,val);
             ~^~
horses.cpp:75:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return f();
            ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:79:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     up(1,0,n-1,pos,pos,val);
            ~^~
horses.cpp:80:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return f();
            ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:89:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         up2(1,0,n-1,i,i,X[i]);
                 ~^~
horses.cpp:93:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         up(1,0,n-1,i,i,Y[i]);
                ~^~
horses.cpp:95:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return f();
            ~^~

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