Submission #200312

#	Time	Username	Problem	Language	Result	Execution time	Memory
200312		Mercenary	Horses (IOI15_horses)	C++14	100 / 100	417 ms	80120 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];
struct node{
    int s , lz;
    ld mx , mlz;
}s[maxn * 4];
ii val[maxn];
int n;

void build(int x , int l , int r){
    s[x].lz = 1;
    if(l == r){
        s[x].s = (ll)p[l] * val[l].second % mod;
        s[x].mx = a[l] + log2(val[l].second);
        return;
    }
    int mid = l + r >> 1;
    build(x*2,l,mid);build(x*2+1,mid+1,r);
    if(s[x * 2].mx > s[x * 2 + 1].mx){
        s[x] = s[x * 2];
    }else{
        s[x] = s[x * 2 + 1];
    }
}

void push(int x , bool key){
    s[x].mx += s[x].mlz;
    s[x].s = (ll)s[x].s * s[x].lz % mod;
    if(key){
        s[x * 2].mlz += s[x].mlz;
        s[x * 2 + 1].mlz += s[x].mlz;
        s[x * 2].lz = (ll)s[x * 2].lz * s[x].lz % mod;
        s[x * 2 + 1].lz = (ll)s[x * 2 + 1].lz * s[x].lz % mod;
    }
    s[x].mlz = 0;s[x].lz = 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){
        s[x].mlz += aa;
        s[x].lz = (ll)s[x].lz * 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(s[x * 2].mx > s[x * 2 + 1].mx){
        s[x] = s[x * 2];
    }else{
        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].s;
}

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].s;
}

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].s;
}

#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:35:43: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         s[x].s = (ll)p[l] * val[l].second % mod;
                  ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
horses.cpp: In function 'void push(int, bool)':
horses.cpp:50:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     s[x].s = (ll)s[x].s * s[x].lz % mod;
              ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:54:49: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         s[x * 2].lz = (ll)s[x * 2].lz * s[x].lz % mod;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:55:57: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         s[x * 2 + 1].lz = (ll)s[x * 2 + 1].lz * s[x].lz % mod;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int, int)':
horses.cpp:67:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         s[x].lz = (ll)s[x].lz * bb % mod;
                   ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:88: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:94:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:29:4: note: shadowed declaration is here
 ii val[maxn];
    ^~~
horses.cpp:96: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:100: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:106:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:29:4: note: shadowed declaration is here
 ii val[maxn];
    ^~~
horses.cpp:108: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:112: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: 23 / 23