Submission #200311

#	Time	Username	Problem	Language	Result	Execution time	Memory
200311		Mercenary	Horses (IOI15_horses)	C++14	77 / 100	422 ms	60152 KiB

horses

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

#ifndef LOCAL
#include "horses.h"
#endif // LOCAL
typedef long long ll;
typedef long double ld;

typedef pair<int,int> ii;
#define pb push_back
#define mp make_pair
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;

int Pow(int x , int y){
    if(y == 0)return 1;
    int r = Pow(x,y/2);
    if(y & 1)return (ll)r * r % mod * x % mod;
    return (ll)r * r % mod;
}

ld a[maxn];
int p[maxn];
int s[maxn * 4] , lz[maxn * 4];
ld mx[maxn * 4] , mlz[maxn * 4];
ii val[maxn];
int n;

void build(int x , int l , int r){
    lz[x] = 1;
    if(l == r){
        mx[x] = a[l] + log2(val[l].second);
        s[x] = (ll)p[l] * val[l].second % mod;
        return;
    }
    int mid = l + r >> 1;
    build(x*2,l,mid);build(x*2+1,mid+1,r);
    if(mx[x * 2] > mx[x * 2 + 1]){
        mx[x] = mx[x * 2];s[x] = s[x * 2];
    }else{
        mx[x] = mx[x * 2 + 1];s[x] = s[x * 2 + 1];
    }
}
void push(int x , bool key){
    mx[x] += mlz[x];
    s[x] = (ll)s[x] * lz[x] % mod;
    if(key){
        mlz[x * 2] += mlz[x];
        mlz[x * 2 + 1] += mlz[x];
        lz[x * 2] = (ll)lz[x * 2] * lz[x] % mod;
        lz[x * 2 + 1] = (ll)lz[x * 2 + 1] * lz[x] % mod;
    }
    mlz[x] = 0;lz[x] = 1;
}
int L , R , bb;
ld aa;

void update(int x ,int l , int r){
    push(x,l!=r);
    if(l > R || L > r)return;
    if(L <= l && r <= R){
        mlz[x] += aa;
        lz[x] = (ll)lz[x] * bb % mod;
        push(x,l!=r);
        return;
    }
    int mid = l + r >> 1;
    update(x*2,l,mid);
    update(x*2+1,mid+1,r);
    if(mx[x * 2] > mx[x * 2 + 1]){
        mx[x] = mx[x * 2];s[x] = s[x * 2];
    }else{
        mx[x] = mx[x * 2 + 1];s[x] = s[x * 2 + 1];
    }
}
int init(int N, int X[], int Y[]) {
    p[0] = 1;
    n = N;
    for(int i = 1 ; i <= n ; ++i){
        val[i] = mp(X[i - 1] , Y[i - 1]);
    }
    for(int i = 1 ; i <= n ; ++i){
        a[i] = a[i - 1] + log2(val[i].first);
        p[i] = (ll)p[i - 1] * val[i].first % mod;
    }
    build(1,1,n);
    return s[1];
}

int updateX(int pos, int val) {
    pos++;
    ld a = -log2(::val[pos].first);
    int b = Pow(::val[pos].first,mod-2);
    ::val[pos].first = val;
    a += log2(::val[pos].first);
    b = (ll)b * ::val[pos].first % mod;
    L = pos;R = n;aa = a;bb = b;
    update(1,1,n);
	return s[1];
}

int updateY(int pos, int val) {
    pos++;
    ld a = -log2(::val[pos].second);
    int b = Pow(::val[pos].second,mod-2);
    ::val[pos].second = val;
    a += log2(::val[pos].second);
    b = (ll)b * ::val[pos].second % mod;
    L = pos;R = pos;aa = a;bb = b;
    update(1,1,n);
	return s[1];
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("a.inp", "r")) {
        freopen("a.inp", "r", stdin);
        freopen("a.out", "w", stdout);
    }
    int N; cin >> N;
	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
	for (int i = 0; i < N; i++) {
        cin >> X[i];
	}
	for (int i = 0; i < N; i++) {
        cin >> Y[i];
	}
    cout << init(N,X,Y) << endl;
	int M;cin >> M;
	for (int i = 0; i < M; i++) {
        int pos , val , type;
        cin >> type >> pos >> val;
		if (type == 1) {
			cout << updateX(pos,val) << endl;
		} else if (type == 2) {
			cout << updateY(pos,val) << endl;
		}
	}

	return 0;
}
#endif // LOCAL

Compilation message (stderr)

horses.cpp: In function 'int Pow(int, int)':
horses.cpp:19:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     if(y & 1)return (ll)r * r % mod * x % mod;
                     ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:20:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return (ll)r * r % mod;
            ~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:34:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         s[x] = (ll)p[l] * val[l].second % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
horses.cpp: In function 'void push(int, bool)':
horses.cpp:47:29: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     s[x] = (ll)s[x] * lz[x] % mod;
            ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:51:43: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         lz[x * 2] = (ll)lz[x * 2] * lz[x] % mod;
                     ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:52:51: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         lz[x * 2 + 1] = (ll)lz[x * 2 + 1] * lz[x] % mod;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int, int)':
horses.cpp:64:32: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         lz[x] = (ll)lz[x] * bb % mod;
                 ~~~~~~~~~~~~~~~^~~~~
horses.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:44: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         p[i] = (ll)p[i - 1] * val[i].first % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:91:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:27:4: note: shadowed declaration is here
 ii val[maxn];
    ^~~
horses.cpp:93:8: warning: declaration of 'a' shadows a global declaration [-Wshadow]
     ld a = -log2(::val[pos].first);
        ^
horses.cpp:23:4: note: shadowed declaration is here
 ld a[maxn];
    ^
horses.cpp:97:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     b = (ll)b * ::val[pos].first % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:27:4: note: shadowed declaration is here
 ii val[maxn];
    ^~~
horses.cpp:105:8: warning: declaration of 'a' shadows a global declaration [-Wshadow]
     ld a = -log2(::val[pos].second);
        ^
horses.cpp:23:4: note: shadowed declaration is here
 ld a[maxn];
    ^
horses.cpp:109:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     b = (ll)b * ::val[pos].second % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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