oj.uz

Submission #847792

# Submission time Handle Problem Language Result Execution time Memory
847792 2023-09-10T12:23:07 Z YassirSalama Game (IOI13_game) C++17
63 / 100
 1223 ms 256000 KB 
#include "game.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;}
struct Node_y{
    ll val;
    Node_y* left,*right;
    Node_y() {
        val=0LL;
        left=(nullptr),right=(nullptr);
    }
};
struct Node_x{
    Node_y* node;
    Node_x* left;
    Node_x* right;
    Node_x() : node(new Node_y()),left(nullptr),right(nullptr) {}
};
Node_x* root;
int n,m;
#define op(a,b) gcd2(a,b)
ll get(Node_y* node,int l,int r,int ql){
    if(node==nullptr) return 0LL;
    if(l==r) 
        return node->val;
    int mid=(l+r)/2;
    if(ql<=mid){
        if(node->left==nullptr) return 0;
        return get(node->left,l,mid,ql);
    }else{
        if(node->right==nullptr) return 0;
        return get(node->right,mid+1,r,ql);
    }
}
void update_y(Node_x* node,int lx,int rx,Node_y* nodey,int ly,int ry,int i,int j,ll x){
    if(ly==ry){
        if(lx==rx){
            nodey->val=x;
        }else{
            ll ans=0;
            if(node->left==nullptr)
                ans=ans;
            else ans=op(ans,get(node->left->node,0,m-1,ly));
            if(node->right==nullptr)
                ans=ans;
            else ans=op(ans,get(node->right->node,0,m-1,ly));
            nodey->val=ans;
        }
        return;
    }
    int mid=(ly+ry)/2;
    if(j<=mid){
        if(nodey->left==nullptr) nodey->left=new Node_y();
        update_y(node,lx,rx,nodey->left,ly,mid,i,j,x);
    }else{
        if(nodey->right==nullptr) nodey->right=new Node_y();
        update_y(node,lx,rx,nodey->right,mid+1,ry,i,j,x);
    }
    ll ans=0;
    if(nodey->left==nullptr) ans=ans;
    else ans=op(ans,nodey->left->val);
    if(nodey->right==nullptr) ans=ans;
    else ans=op(ans,nodey->right->val);
    nodey->val=ans;
}
void update_x(Node_x* node,int l,int r,int i,int j,ll x){
    if(l!=r){
        int mid=(l+r)/2;
        if(i<=mid){
            if(node->left==nullptr) node->left=new Node_x();
            update_x(node->left,l,mid,i,j,x);
        }else{
            if(node->right==nullptr) node->right=new Node_x();
            update_x(node->right,mid+1,r,i,j,x);
        }
    }
    if(node->node==nullptr){
        node->node=new Node_y();
    }
    update_y(node,l,r,node->node,0,m-1,i,j,x);
}
ll ans=0;
ll query_y(Node_y* node,int l,int r,int x1,int y1,int x2,int y2){
    if(y1<=l&&r<=y2) return node->val;
    int mid=(l+r)/2;
    if(y1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=op(ans,query_y(node->left,l,mid,x1,y1,x2,y2));
    }
    if(y2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_y(node->right,mid+1,r,x1,y1,x2,y2));
    }
    return ans;
}
ll query_x(Node_x* node,int l,int r,int x1,int y1,int x2,int y2){
    if(x1<=l&&r<=x2){
        if(node->node==nullptr) return 0LL;
        return query_y(node->node,0,m-1,x1,y1,x2,y2);
    }
    int mid=(l+r)/2;
    if(x1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=op(ans,query_x(node->left,l,mid,x1,y1,x2,y2));
    }
    if(x2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_x(node->right,mid+1,r,x1,y1,x2,y2));
    }
    return ans;
}
void init(int R, int C) {
    n=R;
    m=C;
    root=new Node_x();
}

void update(int P, int Q, long long K) {
    update_x(root,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    ans=0;
    return query_x(root,0,n-1,P,Q,U,V);
}




#ifdef IOI
#include <stdio.h>
#include <stdlib.h>
#include "game.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
    int res;

    FILE *f = fopen("game.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &R);
    res = fscanf(f, "%d", &C);
    res = fscanf(f, "%d", &N);

    init(R, C);

    for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
            res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
            res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        } else
            fail("Invalid action type in input file.");
    }
    fclose(f);

    return 0;
}

#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 379 ms 12628 KB Output is correct
5 Correct 284 ms 12884 KB Output is correct
6 Correct 276 ms 9784 KB Output is correct
7 Correct 302 ms 9688 KB Output is correct
8 Correct 222 ms 6736 KB Output is correct
9 Correct 294 ms 9648 KB Output is correct
10 Correct 283 ms 9584 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 627 ms 15956 KB Output is correct
13 Correct 1004 ms 6292 KB Output is correct
14 Correct 188 ms 848 KB Output is correct
15 Correct 1155 ms 8724 KB Output is correct
16 Correct 154 ms 18184 KB Output is correct
17 Correct 439 ms 11448 KB Output is correct
18 Correct 681 ms 18756 KB Output is correct
19 Correct 620 ms 18784 KB Output is correct
20 Correct 570 ms 18004 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 388 ms 12996 KB Output is correct
13 Correct 272 ms 13056 KB Output is correct
14 Correct 287 ms 9964 KB Output is correct
15 Correct 291 ms 9716 KB Output is correct
16 Correct 220 ms 6728 KB Output is correct
17 Correct 300 ms 9808 KB Output is correct
18 Correct 272 ms 9552 KB Output is correct
19 Correct 639 ms 16032 KB Output is correct
20 Correct 989 ms 6432 KB Output is correct
21 Correct 197 ms 940 KB Output is correct
22 Correct 1155 ms 8840 KB Output is correct
23 Correct 146 ms 18184 KB Output is correct
24 Correct 447 ms 11692 KB Output is correct
25 Correct 706 ms 18788 KB Output is correct
26 Correct 606 ms 18888 KB Output is correct
27 Correct 580 ms 18000 KB Output is correct
28 Correct 612 ms 256000 KB Output is correct
29 Runtime error 1130 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 385 ms 12600 KB Output is correct
13 Correct 269 ms 12848 KB Output is correct
14 Correct 285 ms 9876 KB Output is correct
15 Correct 315 ms 9716 KB Output is correct
16 Correct 222 ms 6688 KB Output is correct
17 Correct 313 ms 9808 KB Output is correct
18 Correct 280 ms 9296 KB Output is correct
19 Correct 646 ms 16012 KB Output is correct
20 Correct 992 ms 6060 KB Output is correct
21 Correct 193 ms 1048 KB Output is correct
22 Correct 1164 ms 8800 KB Output is correct
23 Correct 148 ms 18256 KB Output is correct
24 Correct 444 ms 11468 KB Output is correct
25 Correct 766 ms 18472 KB Output is correct
26 Correct 579 ms 18768 KB Output is correct
27 Correct 591 ms 18136 KB Output is correct
28 Correct 599 ms 256000 KB Output is correct
29 Runtime error 1223 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -