oj.uz

Submission #928743

# Submission time Handle Problem Language Result Execution time Memory
928743 2024-02-17T03:47:54 Z User0069 Horses (IOI15_horses) C++17
17 / 100
 87 ms 50324 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4792 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4696 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4540 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 50324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4640 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4600 KB Output is correct
7 Correct 1 ms 4544 KB Output is correct
8 Correct 1 ms 4548 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4540 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4696 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -