oj.uz

Submission #847829

# Submission time Handle Problem Language Result Execution time Memory
847829 2023-09-10T14:01:31 Z YassirSalama Game (IOI13_game) C++17
63 / 100
 1254 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);
    }
}
int i;int j;ll x;
void update_y(Node_x* node,int lx,int rx,Node_y* nodey,int ly,int ry){
    if(ly==ry){
        if(lx==rx){
            nodey->val=x;
        }else{
            nodey->val=0;
            if(node->left==nullptr)
                nodey->val=nodey->val;
            else nodey->val=op(nodey->val,get(node->left->node,0,m-1,ly));
            if(node->right==nullptr)
                nodey->val=nodey->val;
            else nodey->val=op(nodey->val,get(node->right->node,0,m-1,ly));
        }
        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);
    }else{
        if(nodey->right==nullptr) nodey->right=new Node_y();
        update_y(node,lx,rx,nodey->right,mid+1,ry);
    }
    nodey->val=0;
    if(nodey->left==nullptr) nodey->val=nodey->val;
    else nodey->val=op(nodey->val,nodey->left->val);
    if(nodey->right==nullptr) nodey->val=nodey->val;
    else nodey->val=op(nodey->val,nodey->right->val);
}
void update_x(Node_x* node,int l,int r){
    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);
        }else{
            if(node->right==nullptr) node->right=new Node_x();
            update_x(node->right,mid+1,r);
        }
    }
    if(node->node==nullptr){
        node->node=new Node_y();
    }
    update_y(node,l,r,node->node,0,m-1);
}
ll ans=0;
int x1;int Y1;int x2;int y2;
ll query_y(Node_y* node,int l,int r){
    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));
    }
    if(y2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_y(node->right,mid+1,r));
    }
    return ans;
}
ll query_x(Node_x* node,int l,int r){
    if(x1<=l&&r<=x2){
        if(node->node==nullptr) return 0LL;
        return query_y(node->node,0,m-1);
    }
    int mid=(l+r)/2;
    if(x1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=op(ans,query_x(node->left,l,mid));
    }
    if(x2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_x(node->right,mid+1,r));
    }
    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) {
    i=P;
    j=Q;
    x=K;
    update_x(root,0,n-1);
}

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




#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 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 379 ms 12600 KB Output is correct
5 Correct 273 ms 13248 KB Output is correct
6 Correct 281 ms 9748 KB Output is correct
7 Correct 302 ms 9472 KB Output is correct
8 Correct 225 ms 6824 KB Output is correct
9 Correct 349 ms 9912 KB Output is correct
10 Correct 286 ms 9300 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.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 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 618 ms 15964 KB Output is correct
13 Correct 984 ms 6364 KB Output is correct
14 Correct 190 ms 848 KB Output is correct
15 Correct 1106 ms 9064 KB Output is correct
16 Correct 170 ms 18260 KB Output is correct
17 Correct 476 ms 11604 KB Output is correct
18 Correct 906 ms 18832 KB Output is correct
19 Correct 726 ms 18648 KB Output is correct
20 Correct 698 ms 18132 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 344 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 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 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 386 ms 12680 KB Output is correct
13 Correct 269 ms 13204 KB Output is correct
14 Correct 301 ms 9808 KB Output is correct
15 Correct 340 ms 9604 KB Output is correct
16 Correct 220 ms 6736 KB Output is correct
17 Correct 331 ms 9836 KB Output is correct
18 Correct 368 ms 9280 KB Output is correct
19 Correct 616 ms 15972 KB Output is correct
20 Correct 972 ms 6272 KB Output is correct
21 Correct 191 ms 1060 KB Output is correct
22 Correct 1107 ms 8768 KB Output is correct
23 Correct 161 ms 18256 KB Output is correct
24 Correct 464 ms 11488 KB Output is correct
25 Correct 909 ms 18768 KB Output is correct
26 Correct 718 ms 18732 KB Output is correct
27 Correct 676 ms 18032 KB Output is correct
28 Correct 695 ms 251716 KB Output is correct
29 Runtime error 1254 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 756 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 375 ms 12628 KB Output is correct
13 Correct 260 ms 12876 KB Output is correct
14 Correct 321 ms 9976 KB Output is correct
15 Correct 362 ms 9648 KB Output is correct
16 Correct 217 ms 6580 KB Output is correct
17 Correct 358 ms 10016 KB Output is correct
18 Correct 293 ms 9312 KB Output is correct
19 Correct 643 ms 15952 KB Output is correct
20 Correct 941 ms 6476 KB Output is correct
21 Correct 201 ms 880 KB Output is correct
22 Correct 1127 ms 8848 KB Output is correct
23 Correct 162 ms 18180 KB Output is correct
24 Correct 462 ms 11388 KB Output is correct
25 Correct 946 ms 18596 KB Output is correct
26 Correct 912 ms 18648 KB Output is correct
27 Correct 602 ms 18212 KB Output is correct
28 Correct 692 ms 251928 KB Output is correct
29 Runtime error 1224 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -