Submission #1121924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121924		SalihSahin	Horses (IOI15_horses)	C++14	54 / 100	1573 ms	75064 KiB

horses

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "horses.h"
 
const long long mod = 1e9 + 7;

struct SEGTWALK{
    vector<int> tree, tree2;

    void init(int n){
        tree.assign(4*n, 0);
        tree2.assign(4*n, 0);
    }

    void update(int ind, int l, int r, int pos, int val){
        if(l == r){
            tree[ind] = val;
            tree2[ind] = (val > 1);
        }
        else{
            int m = (l + r)/2;

            if(pos <= m) update(ind*2, l, m, pos, val);
            else update(ind*2+1, m+1, r, pos, val);

            tree[ind] = max(tree[ind*2], tree[ind*2+1]);
            tree2[ind] = (tree2[ind*2] + tree2[ind*2+1]);
        }
    }

    int querymax(int ind, int l, int r, int ql, int qr){
        if(l > r || ql > qr || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;

            return max(querymax(ind*2, l, m, ql, qr), querymax(ind*2+1, m+1, r, ql, qr));
        }
    }

    int queryL(int ind, int l, int r, int pos){
        return 0; // sonra
    }
};

struct SEGT{
    vector<__int128> tree;

    void init(int n){
        tree.assign(4*n, 0);
    }

    void update(int ind, int l, int r, int pos, int val){
        if(l == r){
            tree[ind] = val;
        }
        else{
            int m = (l + r)/2;

            if(pos <= m) update(ind*2, l, m, pos, val);
            else update(ind*2+1, m+1, r, pos, val);

            tree[ind] = (tree[ind*2] * tree[ind*2+1])%mod;
        }
    }

    __int128 query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql || ql > qr) return 1;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;

            return (query(ind*2, l, m, ql, qr) * query(ind*2+1, m+1, r, ql, qr))%mod;
        }
    }
};
 
vector<array<__int128, 2> > arr;
int n;
SEGT seg;
SEGTWALK segwalk;

int init(int N, int X[], int Y[]){
    arr.resize(N);
    n = N;
    seg.init(N);
    segwalk.init(N);
    for(int i = 0; i < N; i++){
        arr[i] = {X[i], Y[i]};
        seg.update(1, 1, N, i+1, arr[i][0]);
        segwalk.update(1, 1, N, i+1, arr[i][1]);
    }
 
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateX(int pos, int val) { 
    int N = n;
    arr[pos][0] = val;
    seg.update(1, 1, N, pos+1, val);
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateY(int pos, int val){
    int N = n;
    arr[pos][1] = val;
    segwalk.update(1, 1, N, pos+1, arr[pos][1]);
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}

Compilation message (stderr)

horses.cpp: In member function 'int SEGTWALK::queryL(int, int, int, int)':
horses.cpp:42:20: warning: unused parameter 'ind' [-Wunused-parameter]
   42 |     int queryL(int ind, int l, int r, int pos){
      |                ~~~~^~~
horses.cpp:42:29: warning: unused parameter 'l' [-Wunused-parameter]
   42 |     int queryL(int ind, int l, int r, int pos){
      |                         ~~~~^
horses.cpp:42:36: warning: unused parameter 'r' [-Wunused-parameter]
   42 |     int queryL(int ind, int l, int r, int pos){
      |                                ~~~~^
horses.cpp:42:43: warning: unused parameter 'pos' [-Wunused-parameter]
   42 |     int queryL(int ind, int l, int r, int pos){
      |                                       ~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:43: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   91 |         seg.update(1, 1, N, i+1, arr[i][0]);
      |                                           ^
horses.cpp:92:47: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   92 |         segwalk.update(1, 1, N, i+1, arr[i][1]);
      |                                               ^
horses.cpp:116:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  116 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:145:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  145 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:47: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
  152 |     segwalk.update(1, 1, N, pos+1, arr[pos][1]);
      |                                               ^
horses.cpp:174:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  174 |     int res = ans;
      |               ^~~

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