oj.uz

Submission #529851

# Submission time Handle Problem Language Result Execution time Memory
529851 2022-02-23T19:02:31 Z ammar2000 Bridges (APIO19_bridges) C++17
16 / 100
 323 ms 5756 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=4e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,m,a[SI],st[SI],RQ,LQ;
void build(int x,int l,int r)
{
    if (l==r)
    {
        st[x]=a[l];
        return ;
    }
    ll m=(l+r)/2;
    build (2*x,l,m);
    build (2*x+1,m+1,r);
    st[x]=min(st[2*x],st[2*x+1]);
}
void update(int x,int l,int r,int in)
{
    if (l==r)
    {
        st[x]=a[l];
        return ;
    }
    ll m=(l+r)/2;
    if (in<=m)
        update(2*x,l,m,in);
    else update (2*x+1,m+1,r,in);
    st[x]=min(st[2*x],st[2*x+1]);
}
void rq(int x,int l,int r,int ql,int v)
{
    if (r<ql)
        return ;
    if (l==r)
    {
        if (st[x]<v)
            RQ=l;
        return ;
    }
    ll m=(l+r)/2;
    if (ql>m)
    {
        if (st[2*x+1]>=v)
            return ;
        else rq(2*x+1,m+1,r,ql,v);
    }
    if (RQ)
        return ;
    //cout <<st[2*x]<<"\n";
    if (st[2*x]<v)
      rq (2*x,l,m,ql,v);
    if (RQ)
        return ;
    rq(2*x+1,m+1,r,ql,v);
}
void lq (int x,int l,int r,int qr ,ll v)
{
    if (l>qr)
        return;
    if (l==r)
    {
        if (st[x]<v)
        LQ=l;
        return ;
    }
    ll m=(l+r)/2;
    if (qr<m+1)
    {
        if (st[2*x]>=v)
            return ;
        lq(2*x,l,m,qr,v);
    }
    if(LQ)
        return ;
    if (st[2*x+1]<v)
        lq(2*x+1,m+1,r,qr,v);
    if (LQ)
        return ;
    lq(2*x,l,m,qr,v);
}
int main()
{
   //fast
   cin>>n>>m;
   for (int i=1;i<=m;i++)
   {
       ll e;
       cin>>e>>e>>e;
       a[i]=e;
   }
   swap(m,n);
   ll N=1;
   while (N<n)
    N*=2;
   build (1,1,N);
   ll q;
   cin>>q;
   while (q--)
   {
       ll t,x,y;
       cin>>t>>x>>y;
       if (t==1)
        {a[x]=y;
        update (1,1,N,x);
        continue ;}
        RQ=LQ=0;
        rq(1,1,N,x,y);
        if (RQ==0)
            RQ=n+1;
        if (x>1)
        lq(1,1,N,x-1,y);
         cout <<RQ-LQ<<"\n";
   }
   // use scanf not cin
   return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 4124 KB Output is correct
2 Correct 239 ms 4260 KB Output is correct
3 Correct 206 ms 4336 KB Output is correct
4 Correct 207 ms 4180 KB Output is correct
5 Correct 205 ms 4220 KB Output is correct
6 Correct 186 ms 4528 KB Output is correct
7 Correct 198 ms 4460 KB Output is correct
8 Correct 195 ms 4436 KB Output is correct
9 Correct 190 ms 1828 KB Output is correct
10 Correct 162 ms 3524 KB Output is correct
11 Correct 166 ms 3396 KB Output is correct
12 Correct 251 ms 4856 KB Output is correct
13 Correct 176 ms 4204 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 4124 KB Output is correct
2 Correct 239 ms 4260 KB Output is correct
3 Correct 206 ms 4336 KB Output is correct
4 Correct 207 ms 4180 KB Output is correct
5 Correct 205 ms 4220 KB Output is correct
6 Correct 186 ms 4528 KB Output is correct
7 Correct 198 ms 4460 KB Output is correct
8 Correct 195 ms 4436 KB Output is correct
9 Correct 190 ms 1828 KB Output is correct
10 Correct 162 ms 3524 KB Output is correct
11 Correct 166 ms 3396 KB Output is correct
12 Correct 251 ms 4856 KB Output is correct
13 Correct 176 ms 4204 KB Output is correct
14 Incorrect 189 ms 3360 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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