Submission #928743

#	Time	Username	Problem	Language	Result	Execution time	Memory
928743		User0069	Horses (IOI15_horses)	C++17	17 / 100	87 ms	50324 KiB

horses

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e6+1;
const int INF=1e9;
const int mod=1e9+7;
int n,x[maxn],y[maxn];
struct num
{
    int a,b;
};
bool operator <(num x,num y)
{
    return x.a<y.a||(x.a==y.a&&x.b<y.b);
}
num operator *(num x,num y)
{
    return {(x.a||y.a||(x.b*y.b>=mod)),x.b*y.b%mod};
}
struct node
{
    num pre,suf,sum,val;
}ST[4*maxn];
node operator +(node a,node b)
{
    node res;
    if(!(a.val<a.suf*b.pre*b.val))
    {
        res.pre=a.pre;
        res.val=a.val;
        res.sum=a.sum*b.sum;
        res.suf=a.suf*b.sum;
    }
    else
    {
        res.val=b.val;
        res.suf=b.suf;
        res.sum=a.sum*b.sum;
        res.pre=b.pre*a.sum;
    }
    return res;
}
void cons(int id,int cl,int cr)
{
    if(cl==cr)
    {
        ST[id].pre=ST[id].sum={0,x[cl]};
        ST[id].suf={0,1};
        ST[id].val={0,y[cl]};
        return;
    }
    int mid=(cl+cr)/2;
    cons(id*2,cl,mid);
    cons(2*id+1,mid+1,cr);
    ST[id]=ST[id*2]+ST[id*2+1];
}
void updatex(int id,int cl,int cr,int pos,int val)
{
    if(cl>pos||cr<pos) return;
    if(cl==cr)
    {
        ST[id].pre=ST[id].sum={0,val};
        return;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) updatex(2*id,cl,mid,pos,val);
    else updatex(2*id+1,mid+1,cr,pos,val);
    ST[id]=ST[id*2]+ST[id*2+1];
}
void updatey(int id,int cl,int cr,int pos,int val)
{
    if(cl>pos||cr<pos) return;
    if(cl==cr)
    {
        ST[id].val={0,val};
        return;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) updatey(2*id,cl,mid,pos,val);
    else updatey(2*id+1,mid+1,cr,pos,val);
    ST[id]=ST[id*2]+ST[id*2+1];
}
int get()
{
    return (ST[1].pre.b*ST[1].val.b)%mod;
}
int init(int _n,int _x[],int _y[])
{
    n=_n;
    for(int i=0;i<n;i++)
    {
        x[i+1]=_x[i];
        y[i+1]=_y[i];
    }
    cons(1,1,n);
    return get();
}
int updateX(int pos,int val)
{
    ++pos;
    updatex(1,1,n,pos,val);
    return get();
}
int updateY(int pos,int val)
{
    ++pos;
    updatey(1,1,n,pos,val);
    return get();
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".OUT","w",stdout);
//    }
//    Faster
//    int _n;
//    cin>>_n;
//    int _x[_n],_y[_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)<<"\n";
//    int m;
//    cin>>m;
//    while(m--)
//    {
//        int type,pos,val;
//        cin>>type>>pos>>val;
//        if(type==1) cout<<updateX(pos,val)<<"\n";
//        else cout<<updateY(pos,val)<<"\n";
//    }
//}

Compilation message (stderr)

horses.cpp: In function 'bool operator<(num, num)':
horses.cpp:23:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   23 | bool operator <(num x,num y)
      |                       ~~~~^
horses.cpp:18:15: note: shadowed declaration is here
   18 | int n,x[maxn],y[maxn];
      |               ^
horses.cpp:23:21: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   23 | bool operator <(num x,num y)
      |                 ~~~~^
horses.cpp:18:7: note: shadowed declaration is here
   18 | int n,x[maxn],y[maxn];
      |       ^
horses.cpp: In function 'num operator*(num, num)':
horses.cpp:27:26: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   27 | num operator *(num x,num y)
      |                      ~~~~^
horses.cpp:18:15: note: shadowed declaration is here
   18 | int n,x[maxn],y[maxn];
      |               ^
horses.cpp:27:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   27 | num operator *(num x,num y)
      |                ~~~~^
horses.cpp:18:7: note: shadowed declaration is here
   18 | int n,x[maxn],y[maxn];
      |       ^

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