oj.uz

답안 #624606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624606 2022-08-08T14:27:47 Z NicolaAbusaad2014 말 (IOI15_horses) C++14
17 / 100
 139 ms 181332 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
struct segment_tree
{
    struct node
    {
        long double value;
        long pos,left,right;
    };
    node dum;
    vector<node>tree;
    vector<long double>upd;
    node operation(node x,node z)
    {
        node ret;
        if(x.value>=z.value){
            ret.value=x.value;
            ret.pos=x.pos;
        }
        else{
            ret.value=z.value;
            ret.pos=z.pos;
        }
        ret.left=min(x.left,z.left);
        ret.right=max(x.right,z.right);
        return ret;
    }
    void push(long node)
    {
        tree[node].value+=upd[node];
        if(node<tree.size()){
            upd[node*2]+=upd[node];
            upd[(node*2)+1]+=upd[node];
        }
        upd[node]=0;
    }
    void build(vector<long double>v)
    {
        tree.clear();
        upd.clear();
        int x=((v.size())*2)-1;
        while(x&(x-1)){
            x=x&(x-1);
        }
        tree.resize(x*2);
        upd.resize(x*2);
        dum.value=-1e9;
        dum.left=-1e9;
        dum.right=1e9;
        for(long i=0;i<v.size();i++){
            tree[i+x].value=v[i];
            tree[i+x].pos=i;
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=v.size();i<x;i++){
            tree[i+x].value=-1e9;
            tree[i+x].pos=i;
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=x-1;i>0;i--){
            tree[i]=operation(tree[i*2],tree[(i*2)+1]);
        }
    }
    node get(int l,int r,int node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return dum;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            return tree[node];
        }
        return operation(get(l,r,node*2),get(l,r,(node*2)+1));
    }
    void update(int l,int r,long double z,int node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            upd[node]+=z;
            push(node);
            return;
        }
        update(l,r,z,node*2);
        update(l,r,z,(node*2)+1);
        tree[node]=operation(tree[node*2],tree[(node*2)+1]);
    }
};
struct segment_tree_mul
{
    struct node
    {
        long long value,left,right;
    };
    node dum;
    vector<node>tree;
    vector<long long>upd;
    node operation(node x,node z)
    {
        node ret;
        ret.value=(x.value*z.value)%mod;
        ret.left=min(x.left,z.left);
        ret.right=max(x.right,z.right);
        return ret;
    }
    void push(long node)
    {
        if(upd[node]!=1){
            tree[node].value*=power(upd[node],tree[node].right-tree[node].left+1);
            tree[node].value%=mod;
            if(node<tree[0].value){
                upd[node*2]*=upd[node];
                upd[node*2]%=mod;
                upd[(node*2)+1]*=upd[node];
                upd[(node*2)+1]%=mod;
            }
            upd[node]=1;
        }
    }
    void build(vector<long long>v)
    {
        tree.clear();
        upd.clear();
        long long x=((v.size())*2)-1;
        while(x&(x-1)){
            x=x&(x-1);
        }
        tree.resize(x*2);
        upd.resize(x*2);
        tree[0].value=x;
        dum.value=1;
        dum.left=-1e18;
        dum.right=1e18;
        for(long i=0;i<v.size();i++){
            upd[i+x]=1;
            tree[i+x].value=v[i];
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=v.size();i<x;i++){
            upd[i+x]=1;
            tree[i+x].value=1;
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=x-1;i>0;i--){
            upd[i]=1;
            tree[i]=operation(tree[i*2],tree[(i*2)+1]);
        }
    }
    node get(long long l,long long r,long node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return dum;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            return tree[node];
        }
        return operation(get(l,r,node*2),get(l,r,(node*2)+1));
    }
    void update(long long l,long long r,long long z,long long node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            upd[node]*=z;
            upd[node]%=mod;
            push(node);
            return;
        }
        update(l,r,z,node*2);
        update(l,r,z,(node*2)+1);
        tree[node]=operation(tree[node*2],tree[(node*2)+1]);
    }
};
segment_tree st;
segment_tree_mul ans;
long n;
vector<long long>x,y,tot;
vector<long double>v;
int init(int N, int X[], int Y[]) {
    n=N;
    x.resize(n);
    y.resize(n);
    tot.resize(n);
    v.resize(n);
    REP(i,0,n){
        x[i]=X[i];
        y[i]=Y[i];
    }
    v[0]=log(x[0])+log(y[0]);
    tot[0]=x[0];
    REP(i,1,n){
        v[i]=v[i-1]+log(x[i])+log(y[i])-log(y[i-1]);
        tot[i]=(tot[i-1]*x[i])%mod;
    }
    st.build(v);
    //ans.build(tot);
    N=st.get(0,n-1).pos;
    return (tot[N]*y[N])%mod;
}

int updateX(int pos, int val) {
	long long V=val;
	st.update(pos,n-1,log(V)-log(x[pos]));
	ans.update(pos,n-1,(V*inv(x[pos]))%mod);
    x[pos]=V;
    V=st.get(0,n-1).pos;
    return (ans.get(V,V).value*y[V])%mod;
}

int updateY(int pos, int val) {
    long long V=val;
	st.update(pos,pos,log(V)-log(y[pos]));
    y[pos]=V;
    V=st.get(0,n-1).pos;
    return (ans.get(V,V).value*y[V])%mod;
}

Compilation message

horses.cpp: In member function 'void segment_tree::push(long int)':
horses.cpp:37:20: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   37 |     void push(long node)
      |               ~~~~~^~~~
horses.cpp:14:12: note: shadowed declaration is here
   14 |     struct node
      |            ^~~~
horses.cpp:40:16: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<segment_tree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if(node<tree.size()){
      |            ~~~~^~~~~~~~~~~~
horses.cpp: In member function 'void segment_tree::build(std::vector<long double>)':
horses.cpp:50:29: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   50 |         int x=((v.size())*2)-1;
      |               ~~~~~~~~~~~~~~^~
horses.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
horses.cpp: In member function 'segment_tree::node segment_tree::get(int, int, int)':
horses.cpp:75:30: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   75 |     node get(int l,int r,int node=1)
      |                          ~~~~^~~~~~
horses.cpp:14:12: note: shadowed declaration is here
   14 |     struct node
      |            ^~~~
horses.cpp: In member function 'void segment_tree::update(int, int, long double, int)':
horses.cpp:86:47: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
   86 |     void update(int l,int r,long double z,int node=1)
      |                                           ~~~~^~~~~~
horses.cpp:14:12: note: shadowed declaration is here
   14 |     struct node
      |            ^~~~
horses.cpp: In member function 'void segment_tree_mul::push(long int)':
horses.cpp:119:20: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  119 |     void push(long node)
      |               ~~~~~^~~~
horses.cpp:104:12: note: shadowed declaration is here
  104 |     struct node
      |            ^~~~
horses.cpp: In member function 'void segment_tree_mul::build(std::vector<long long int>)':
horses.cpp:147:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
horses.cpp: In member function 'segment_tree_mul::node segment_tree_mul::get(long long int, long long int, long int)':
horses.cpp:164:43: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  164 |     node get(long long l,long long r,long node=1)
      |                                      ~~~~~^~~~~~
horses.cpp:104:12: note: shadowed declaration is here
  104 |     struct node
      |            ^~~~
horses.cpp: In member function 'void segment_tree_mul::update(long long int, long long int, long long int, long long int)':
horses.cpp:175:63: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
  175 |     void update(long long l,long long r,long long z,long long node=1)
      |                                                     ~~~~~~~~~~^~~~~~
horses.cpp:104:12: note: shadowed declaration is here
  104 |     struct node
      |            ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:215:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  215 |     N=st.get(0,n-1).pos;
      |                ~^~
horses.cpp:215:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  215 |     N=st.get(0,n-1).pos;
      |       ~~~~~~~~~~~~~~^~~
horses.cpp:216:25: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  216 |     return (tot[N]*y[N])%mod;
      |            ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:221:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  221 |  st.update(pos,n-1,log(V)-log(x[pos]));
      |                ~^~
horses.cpp:224:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  224 |     V=st.get(0,n-1).pos;
      |                ~^~
horses.cpp:225:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  225 |     return (ans.get(V,V).value*y[V])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:232:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  232 |     V=st.get(0,n-1).pos;
      |                ~^~
horses.cpp:233:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  233 |     return (ans.get(V,V).value*y[V])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 308 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 280 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 139 ms 181332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -