Submission #687318

#	Time	Username	Problem	Language	Result	Execution time	Memory
687318		lam	Game (IOI13_game)	C++14	0 / 100	1 ms	324 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
#define ff first
#define ss second
int n,m;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node
{
    node *l, *r;
    vector <pair<ll,int>> a;
    int val;
    node()
    {
        l=r=0;
        a.clear(); val=0;
    }
};

struct node2
{
    node2 *l, *r;
    node *it;
    node2()
    {
        l=r=0;
        it=0;
    }
};

node2 *tree;

ll get_val(node *&x)
{
    return (x)?x->val:0LL;
}

void upd(node *&u, int ly, int ry, int idx, int idy, ll val)
{
    if (!u) u=new node();
    if (ly==ry)
    {
        int j = -1;
        for (int i=0; i<u->a.size(); i++) if (u->a[i].ss == idx) j=i;
        if (j==-1) u->a.push_back({val,idx});
        else u->a[j].ff=val;
        val=0LL;
        for (pair<ll,int> i:u->a) val=gcd2(val,i.ff);
        u->val=val;
        return;
    }
    int mid=(ly+ry)/2;
    if (idy<=mid)
        upd(u->l,ly,mid,idx,idy,val);
    else
        upd(u->r,mid+1,ry,idx,idy,val);
    u->val = gcd2(get_val(u->l),get_val(u->r));
}

void upd2(node2 *&u, int lx, int rx, int idx, int idy, ll val)
{
    if (!u) u=new node2();
    upd(u->it,1,m,idx,idy,val);
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=mid)
        upd2(u->l,lx,mid,idx,idy,val);
    else
        upd2(u->r,mid+1,rx,idx,idy,val);
}

ll get(node *&u, int ly, int ry, int l, int r)
{
    if (!u) return 0LL;
    if (ly>r||ry<l) return 0LL;
    if (ly>=l&&ry<=r) return u->val;
    int mid=(ly+ry)/2;
    return gcd2(get(u->l,ly,mid,l,r),get(u->r,mid+1,ry,l,r));
}

ll get2(node2 *&u, int lx, int rx, int l, int r, int ly, int ry)
{
    if (!u) return 0LL;
    if (lx>r||rx<l) return 0LL;
    if (lx>=l&&rx<=r) return get(u->it,1,m,ly,ry);
    int mid=(lx+rx)/2;
    return gcd2(get2(u->l,lx,mid,l,r,ly,ry),get2(u->r,mid+1,rx,l,r,ly,ry));
}

void init(int R, int C) {
    n=R; m=C;
}

void update(int P, int Q, long long K) {
    P++; Q++; upd2(tree,1,n,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    P++; Q++; U++; V++;
    return get2(tree,1,n,P,U,Q,V);
}


//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr); cout.tie(nullptr);
//    cin>>n>>m;
//    int q; cin>>q;
//    tree=0;
//    while (q--)
//    {
//        int tt; cin>>tt;
//        if (tt==1)
//        {
//            int x,y; ll val;
//            cin>>x>>y>>val;
//            x++; y++;
//            upd2(tree,1,n,x,y,val);
//        }
//        else
//        {
//            int x1, y1, x2, y2;
//            cin>>x1>>y1>>x2>>y2;
//            x1++; y1++; x2++; y2++;
//            ll ans=get2(tree,1,n,x1,x2,y1,y2);
//            cout<<ans<<'\n';
//        }
//    }
//
//}

Compilation message (stderr)

game.cpp: In function 'void upd(node*&, int, int, int, int, long long int)':
game.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i=0; i<u->a.size(); i++) if (u->a[i].ss == idx) j=i;
      |                       ~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20