Submission #396770

#	Time	Username	Problem	Language	Result	Execution time	Memory
396770		ly20	Horses (IOI15_horses)	C++17	17 / 100	83 ms	29892 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 512345, MOD = 1e9 + 7;
int x[MAXN], y[MAXN];
int seg[MAXN];
long long multe[MAXN], multd[MAXN], ide[MAXN], idd[MAXN];
int n;
int acha() {
    return (y[seg[1]] * multe[1]) % MOD;
}
int mult (int a, int b) {
    long long c = ((long long) a * b);
    if(c >= MOD) return MOD;
    else return (int) c;
}
void build(int cur ,int ini, int fim) {
    if(ini == fim) {
        seg[cur] = ini;
        multe[cur] = x[ini];
        multd[cur] = 1;
        return;
    }
    int m = (ini + fim) /2;
    int e = 2 * cur, d = 2 * cur + 1;
    build(e, ini, m); build(d, m + 1, fim);
    int ye = y[seg[e]], yd = y[seg[d]];
    if(ide[d] == 1) {
        seg[cur] = seg[d];
        multe[cur] = (((multe[e] * multd[e]) % MOD) * multe[d]) % MOD;
        multd[cur] = multd[d];
        ide[cur] = 1;
        idd[cur] = idd[d];
        return;
    }
    int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
    if(md > y[seg[e]]) {
        seg[cur] = seg[d];
        multe[cur] = (((multe[e] * multd[e]) % MOD) * multe[d]) % MOD;
        multd[cur] = multd[d];
        if(md == MOD) ide[cur] = 1;
        else ide[cur] = 0;
        idd[cur] = idd[d];
        return;
    }
    else {
        seg[cur] = seg[e];
        int teste = (mult(multd[d], multe[d]), multd[e]);
        multe[cur] = multe[e];
        ide[cur] = ide[e];
        multd[cur] = (((multd[e] * multe[d]) % MOD) * multd[d] )% MOD;
        if(teste == MOD) idd[cur] = 1;
        else idd[cur] = 0;
    }
}
void update(int cur, int ini, int fim, int id) {
    if(ini > id || fim < id) return;
    if(ini == fim) {
        seg[cur] = ini;
        multe[cur] = x[ini];
        multd[cur] = 1;
        return;
    }
    int m = (ini + fim) /2;
    int e = 2 * cur, d = 2 * cur + 1;
    update(e, ini, m, id); update(d, m + 1, fim, id);
    int ye = y[seg[e]], yd = y[seg[d]];
    if(ide[d] == 1) {
        seg[cur] = seg[d];
        multe[cur] = (((multe[e] * multd[e]) % MOD) * multe[d]) % MOD;
        multd[cur] = multd[d];
        ide[cur] = 1;
        idd[cur] = idd[d];
        return;
    }
    int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
    if(md > y[seg[e]]) {
        seg[cur] = seg[d];
        multe[cur] = (((multe[e] * multd[e]) % MOD) * multe[d]) % MOD;
        multd[cur] = multd[d];
        if(md == MOD) ide[cur] = 1;
        else ide[cur] = 0;
        idd[cur] = idd[d];
        return;
    }
    else {
        seg[cur] = seg[e];
        int teste = (mult(multd[d], multe[d]), multd[e]);
        multe[cur] = multe[e];
        ide[cur] = ide[e];
        multd[cur] = (((multd[e] * multe[d]) % MOD) * multd[d] )% MOD;
        if(teste == MOD) idd[cur] = 1;
        else idd[cur] = 0;
    }
}
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
    }
    build(1, 0, n - 1);
	return acha();
}

int updateX(int pos, int val) {
    x[pos] = val;
    update(1, 0, n - 1, pos);
	return acha();
}

int updateY(int pos, int val) {
    y[pos] = val;
    update(1, 0, n - 1, pos);
	return acha();
}
/*int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &y[i]);
    }
    printf("%d\n", init(n, x, y));
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        int tp, pos, val;
        scanf("%d %d %d", &tp, &pos, &val);
        if(tp == 1) printf("%d\n", updateX(pos, val));
        else printf("%d\n", updateY(pos, val));
    }
}*/

Compilation message (stderr)

horses.cpp: In function 'int acha()':
horses.cpp:10:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 |     return (y[seg[1]] * multe[1]) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:36:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   36 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                        ~~~~~~~^
horses.cpp:36:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   36 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                                  ~~~~~~~^
horses.cpp:48:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                           ~~~~~~~^
horses.cpp:48:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                                     ~~~~~~~^
horses.cpp:48:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
horses.cpp:27:9: warning: unused variable 'ye' [-Wunused-variable]
   27 |     int ye = y[seg[e]], yd = y[seg[d]];
      |         ^~
horses.cpp:27:25: warning: unused variable 'yd' [-Wunused-variable]
   27 |     int ye = y[seg[e]], yd = y[seg[d]];
      |                         ^~
horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:76:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                        ~~~~~~~^
horses.cpp:76:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                                  ~~~~~~~^
horses.cpp:88:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                           ~~~~~~~^
horses.cpp:88:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                                     ~~~~~~~^
horses.cpp:88:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
horses.cpp:67:9: warning: unused variable 'ye' [-Wunused-variable]
   67 |     int ye = y[seg[e]], yd = y[seg[d]];
      |         ^~
horses.cpp:67:25: warning: unused variable 'yd' [-Wunused-variable]
   67 |     int ye = y[seg[e]], yd = y[seg[d]];
      |                         ^~

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