Submission #396781

#	Time	Username	Problem	Language	Result	Execution time	Memory
396781		ly20	Horses (IOI15_horses)	C++17	100 / 100	223 ms	58752 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[4 * MAXN];
long long multe[4 * MAXN], multd[4 * MAXN], ide[4 * MAXN], idd[4 * MAXN];
int n;
int acha() {
    //printf("%d\n", seg[1]);
    return ((long long) y[seg[1]] * multe[1]) % MOD;
}
int mult (int a, int b) {
    long long c = ((long long) a * (long long) b);
    if(c >= (long long) 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(mult(multe[e], mult(multd[e], multe[d])) == 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;
        ide[cur] = 0;
        idd[cur] = 0;
        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);
    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(mult(multe[e], mult(multd[e], multe[d])) == 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));
    }
}*/
/*
10
3 2 7 5 11 13 107 23 51 3
1 1 1 1 1000000000 1 1 1 1 1
16
1 1 1
1 2 1
1 0 1
1 8 1
1 7 1
1 9 1
1 1 25
1 8 123456789
1 4 1
1 6 1
1 3 1
1 5 1
1 5 12345
1 6 123456
1 7 1234567
2 4 3
*/

Compilation message (stderr)

horses.cpp: In function 'int acha()':
horses.cpp:11:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |     return ((long long) y[seg[1]] * multe[1]) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:37:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                        ~~~~~~~^
horses.cpp:37:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                                  ~~~~~~~^
horses.cpp:42:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                                ~~~~~~~^
horses.cpp:42:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                                          ~~~~~~~^
horses.cpp:42:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                 ~~~~~~~^
horses.cpp:49:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                           ~~~~~~~^
horses.cpp:49:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                                     ~~~~~~~^
horses.cpp:49:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
horses.cpp:28:9: warning: unused variable 'ye' [-Wunused-variable]
   28 |     int ye = y[seg[e]], yd = y[seg[d]];
      |         ^~
horses.cpp:28:25: warning: unused variable 'yd' [-Wunused-variable]
   28 |     int ye = y[seg[e]], yd = y[seg[d]];
      |                         ^~
horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:78:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                        ~~~~~~~^
horses.cpp:78:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |     int md = mult(mult(multe[d], multd[e]), y[seg[d]]);
      |                                  ~~~~~~~^
horses.cpp:83:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                                ~~~~~~~^
horses.cpp:83:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                                          ~~~~~~~^
horses.cpp:83:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |         if(mult(multe[e], mult(multd[e], multe[d])) == MOD) ide[cur] = 1;
      |                 ~~~~~~~^
horses.cpp:90:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                           ~~~~~~~^
horses.cpp:90:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                                     ~~~~~~~^
horses.cpp:90:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |         int teste = (mult(multd[d], multe[d]), multd[e]);
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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