oj.uz

Submission #69158

# Submission time Handle Problem Language Result Execution time Memory
69158 2018-08-20T08:14:16 Z yusufake Horses (IOI15_horses) C++
0 / 100
 1500 ms 28684 KB 
#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 == tr) 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 == tr) return ss[v];
    return qry2(sol) * qry2(sag) % mod;
}


ll A[77],B[77],l,r,j,n,t,mx;
int 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]);
    }
    //coiiiiut << 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

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 'int f()':
horses.cpp:49: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:49: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:49:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:58: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:58: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:58:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:68: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:68: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:68:38: 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:75:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     up2(1,0,n-1,pos,pos,val);
             ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:80:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     up(1,0,n-1,pos,pos,val);
            ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90: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:94:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         up(1,0,n-1,i,i,Y[i]);
                ~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 2 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct
2 Incorrect 2 ms 564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 28684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28684 KB Output is correct
2 Incorrect 2 ms 28684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 28684 KB Output is correct
2 Incorrect 3 ms 28684 KB Output isn't correct
3 Halted 0 ms 0 KB -