제출 #927977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927977		pan	말 (IOI15_horses)	C++17	100 / 100	545 ms	119892 KiB

horses

#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;
      |         ~~~~~~^~~

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