oj.uz

Submission #977831

# Submission time Handle Problem Language Result Execution time Memory
977831 2024-05-08T11:38:56 Z De3b0o Bridges (APIO19_bridges) C++14
16 / 100
 582 ms 6848 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z%mod*x%mod;
    else
        return z*z%mod;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x%y);
}

ll n , m;
ll val[100009];
ll ans;
ll seg[1000009];

void sb(ll n , ll l , ll r)
{
    if(l==r)
    {
        seg[n]=val[l];
        return;
    }
    sb(lc,l,mid);
    sb(rc,mid+1,r);
    seg[n]=min(seg[lc],seg[rc]);
}

void se(ll n , ll l , ll r , ll idx , ll w)
{
    if(l>idx||r<idx)
        return;
    if(l==r)
    {
        seg[n]=w;
        return;
    }
    se(lc,l,mid,idx,w);
    se(rc,mid+1,r,idx,w);
    seg[n]=min(seg[lc],seg[rc]);
}

ll sg(ll n , ll l , ll r , ll l1 , ll r1)
{
    if(l>r1||r<l1)
        return 1e10;
    if(l>=l1&&r<=r1)
        return seg[n];
    return min(sg(lc,l,mid,l1,r1),sg(rc,mid+1,r,l1,r1));
}

int main()
{
    d3
    cin >> n >> m;
    if(n==1)
    {
        ll q;
        cin >> q;
        while(q--)
        {
            ll t , x , y;
            cin >> t >> x >> y;
            if(t==2)
                cout << 1 << "\n";
        }
        return 0;
    }
    for(int i = 1 ; m>=i ; i++)
    {
        ll eee;
        cin >> eee >> eee >> val[i];
    }
    sb(1,1,n-1);
    ll q;
    cin >> q;
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll idx , w;
            cin >> idx >> w;
            se(1,1,n-1,idx,w);
        }
        else
        {
            ll idx , w;
            cin >> idx >> w;
            ll ans = 1;
            ll l = idx , r = n-1;
            ll y = idx-1;
            while(l<=r)
            {
                ll x = sg(1,1,n-1,idx,mid);
                if(x>=w)
                {
                    y=mid;
                    l=mid+1;
                }
                else
                    r=mid-1;
            }
            ans+=y-(idx-1);
            l = 1 , r = idx-1;
            y=idx;
            while(l<=r)
            {
                ll x = sg(1,1,n-1,mid,idx-1);
                if(x>=w)
                {
                    y=mid;
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            ans+=idx-y;
            cans
        }
    }
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 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 325 ms 5008 KB Output is correct
2 Correct 306 ms 4812 KB Output is correct
3 Correct 307 ms 4700 KB Output is correct
4 Correct 315 ms 4700 KB Output is correct
5 Correct 306 ms 4820 KB Output is correct
6 Correct 348 ms 4764 KB Output is correct
7 Correct 356 ms 5240 KB Output is correct
8 Correct 342 ms 4888 KB Output is correct
9 Correct 24 ms 1556 KB Output is correct
10 Correct 325 ms 6200 KB Output is correct
11 Correct 310 ms 6084 KB Output is correct
12 Correct 580 ms 6848 KB Output is correct
13 Correct 106 ms 6488 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 5008 KB Output is correct
2 Correct 306 ms 4812 KB Output is correct
3 Correct 307 ms 4700 KB Output is correct
4 Correct 315 ms 4700 KB Output is correct
5 Correct 306 ms 4820 KB Output is correct
6 Correct 348 ms 4764 KB Output is correct
7 Correct 356 ms 5240 KB Output is correct
8 Correct 342 ms 4888 KB Output is correct
9 Correct 24 ms 1556 KB Output is correct
10 Correct 325 ms 6200 KB Output is correct
11 Correct 310 ms 6084 KB Output is correct
12 Correct 580 ms 6848 KB Output is correct
13 Correct 106 ms 6488 KB Output is correct
14 Incorrect 293 ms 5036 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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