oj.uz

Submission #88646

# Submission time Handle Problem Language Result Execution time Memory
88646 2018-12-07T08:33:04 Z Bodo171 Simple game (IZhO17_game) C++14
100 / 100
 218 ms 22684 KB 
#include <iostream>
#include <fstream>
using namespace std;
const int lim=1000*1000;
const int nmax=lim+5;
int aib[nmax],a[nmax];
int n,m,i,j,poz,val,x,tip,vv;
inline int lbit(int x)
{
    return (((x^(x-1))&x));
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=lim;idx+=lbit(idx))
        aib[idx]+=val;
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
void add(int l,int r,int val)
{
    if(l>r) swap(l,r);
    update(l,val);
    update(r+1,-val);
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<n;i++)
        add(a[i],a[i+1],1);
    for(i=1;i<=m;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>poz>>val;
            for(vv=-1;vv<=1;vv+=2)
            {
                if(poz>1) add(a[poz-1],a[poz],vv);
                if(poz<n) add(a[poz+1],a[poz],vv);
                a[poz]=val;
            }
        }
        else
        {
            cin>>val;
            cout<<compute(val)<<'\n';
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 6 ms 4288 KB Output is correct
4 Correct 7 ms 4288 KB Output is correct
5 Correct 7 ms 4316 KB Output is correct
6 Correct 6 ms 4412 KB Output is correct
7 Correct 5 ms 4412 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 6 ms 4288 KB Output is correct
4 Correct 7 ms 4288 KB Output is correct
5 Correct 7 ms 4316 KB Output is correct
6 Correct 6 ms 4412 KB Output is correct
7 Correct 5 ms 4412 KB Output is correct
8 Correct 201 ms 4412 KB Output is correct
9 Correct 216 ms 8084 KB Output is correct
10 Correct 218 ms 9740 KB Output is correct
11 Correct 196 ms 9740 KB Output is correct
12 Correct 209 ms 9740 KB Output is correct
13 Correct 208 ms 9740 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 6 ms 4288 KB Output is correct
4 Correct 7 ms 4288 KB Output is correct
5 Correct 7 ms 4316 KB Output is correct
6 Correct 6 ms 4412 KB Output is correct
7 Correct 5 ms 4412 KB Output is correct
8 Correct 201 ms 4412 KB Output is correct
9 Correct 216 ms 8084 KB Output is correct
10 Correct 218 ms 9740 KB Output is correct
11 Correct 196 ms 9740 KB Output is correct
12 Correct 209 ms 9740 KB Output is correct
13 Correct 208 ms 9740 KB Output is correct
14 Correct 171 ms 14948 KB Output is correct
15 Correct 170 ms 16888 KB Output is correct
16 Correct 172 ms 18904 KB Output is correct
17 Correct 168 ms 20744 KB Output is correct
18 Correct 169 ms 22684 KB Output is correct