제출 #927977

#제출 시각아이디문제언어결과실행 시간메모리
927977pan말 (IOI15_horses)C++17
100 / 100
545 ms119892 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#include "bits_stdc++.h" #define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define input(x) scanf("%lld", &x); #define input2(x, y) scanf("%lld%lld", &x, &y); #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z); #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); using namespace std; //using namespace __gnu_pbds; #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> typedef long long ll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<ll, pi> pii; ll const mod = 1e9+7; ll n; vector<ll> x, y; ll inv(ll a) { return a <= 1 ? a : mod - (long long)(mod/a) * inv(mod % a) % mod; } struct node{ int s, e, m; //range is [s,e], m is the middle point ll val, lazy; ld logval, loglazy; //lazy tag of [s,e] node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e] node (int S, int E){ //constructor called node s = S, e = E, m = (s+e)/2; val = 1; logval = 0; //initially all values are 0 lazy = 1; loglazy = (ld) 0.0; //lazy tag of 0 will mean there is no update (sentinel value) if(s != e){ //node is not yet a leaf, so create two children l = new node(s, m); //create left child r = new node(m+1, e); //create right child } } void propogate(){ if (lazy==1 && loglazy == 0) return; //nothing happens val = (val*lazy)%mod;//(e-s+1) is the length of the range logval+=loglazy; if (s != e){ //not a leaf, send lazy tags to children l->lazy = (l->lazy*lazy)%mod; r->lazy = (r->lazy*lazy)%mod; l->loglazy+=loglazy; r->loglazy+=loglazy; } lazy=1; //set our lazy tag value back to the sentinel loglazy = 0; } void update(int S, int E, ll V, ld logv){ //increment [S,E] by V if(s==S && e==E)//update covers range, update lazy tag { lazy = (lazy*(V))%mod; loglazy += logv; } else{ //go we have to go deeper if(E <= m) l->update(S, E, V, logv); //[S,E] is in the left child else if (m < S) r->update(S, E, V, logv); //[S,E] is in the right child else l->update(S, m, V, logv),r->update(m+1, E, V, logv); l->propogate(),r->propogate(); //remember to propogate your children before update yourself if (l-> logval>r->logval) { logval = l-> logval; val = l-> val; } else { logval = r->logval; val = r->val; } } } } *root; int init(int N, int X[], int Y[]) { root = new node(0, N); n=N; x.resize(n); y.resize(n); for (ll i=0; i<n; ++i) x[i] = X[i]; for (ll i=0; i<n; ++i) y[i] = Y[i]; ll val = 1; ld logval = 0.0; for (ll i=0; i<n; ++i) { val = (val*X[i])%mod; logval+=logl(X[i]); root->update(i, i, (val*(Y[i]%mod))%mod, logval + logl(Y[i])); } root->propogate(); return root-> val; } int updateX(int pos, int val) { root->update(pos, n-1, (inv(x[pos])*(val%mod))%mod, logl(val)-logl(x[pos])); x[pos] = val; root->propogate(); return root->val; } int updateY(int pos, int val) { root->update(pos, pos, (inv(y[pos])*(val%mod))%mod, logl(val)-logl(y[pos])); y[pos]= val; root->propogate(); return root->val; }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:110:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |   root->update(i, i, (val*(Y[i]%mod))%mod, logval + logl(Y[i]));
      |                ^
horses.cpp:110:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |   root->update(i, i, (val*(Y[i]%mod))%mod, logval + logl(Y[i]));
      |                   ^
horses.cpp:113:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |  return root-> val;
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:118:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  root->update(pos, n-1, (inv(x[pos])*(val%mod))%mod, logl(val)-logl(x[pos]));
      |                    ~^~
horses.cpp:121:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  121 |  return root->val;
      |         ~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  return root->val;
      |         ~~~~~~^~~
#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...