Submission #200312

#TimeUsernameProblemLanguageResultExecution timeMemory
200312MercenaryHorses (IOI15_horses)C++14
100 / 100
417 ms80120 KiB
#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;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...