oj.uz

답안 #93653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93653 2019-01-10T14:33:59 Z ajmasin Relativnost (COCI15_relativnost) C++14
140 / 140
 2253 ms 23032 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)


const int maxn = 100100;
const int maxc = 21;
const int offset = (1<<17);
const int mod = 10007;

int n, c, q;

int niza[maxn];
int nizb[maxn], suma[maxc][maxc];

inline int add(const int &a,const int &b)
{
    if(a + b >= mod) return a + b - mod;
    return a + b;
}

inline int mult(const int &a,const int &b)
{
    return a * b % mod;
}

struct tournament
{
    int brn[2 * offset][maxc];
    void update(int cvor)
    {
        REP(i, 0, c + 1) brn[cvor][i] = 0;
        REP(i, 0, c + 1)
        {
            REP(j, 0, c + 1)
            {
                brn[cvor][suma[i][j]] = add(brn[cvor][suma[i][j]], mult(brn[cvor * 2][i], brn[cvor * 2 + 1][j]));
            }
        }
        return;
    }
}T;

bool ok(char znak)
{
    if (znak >= '0' && znak <= '9') return 1;
    return 0;
}

int dajbroj()
{
    int ret = 0;
    char in;

    while(!ok(in = getchar_unlocked()));
    ret += in - '0';
    while(ok(in = getchar_unlocked()))
    {
        ret *= 10;
        ret += in - '0';
    }
    return ret;
}

int main()
{
    for(int i = 2 * offset - 1; i >= offset; i--) T.brn[i][0] = 1;
    n = dajbroj();
    c = dajbroj();
    for(int i = 0;i<=c;i++){
        for(int j = 0;j<=c;j++) {
            suma[i][j] = min(i + j, c);
        }
    }
    int a, b;
    REP(i, 0, n)
    {
        //scanf("%d", &niza[i]);
        niza[i] = dajbroj();
        niza[i] %= mod;
    }
    REP(i, 0, n)
    {
        //scanf("%d", &nizb[i]);
        nizb[i] = dajbroj();
        nizb[i] %= mod;
    }
    REP(i, 0, n)
    {
        T.brn[i + offset][0] = nizb[i];
        T.brn[i + offset][1] = niza[i];
    }
    for(int i = offset - 1; i > 0; i--) T.update(i);
    q = dajbroj();
    int p;
    REP(i, 0, q)
    {
        //scanf("%d%d%d", &p, &a, &b);
        p = dajbroj();
        a = dajbroj();
        b = dajbroj();
        a %= mod;
        b %= mod;
        p--;
        T.brn[p + offset][0] = b;
        T.brn[p + offset][1] = a;
        p += offset;
        p /= 2;
        while(p)
        {
            T.update(p);
            p /= 2;
        }
        printf("%d\n", T.brn[1][c]);
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 21880 KB Output is correct
2 Correct 86 ms 21880 KB Output is correct
3 Correct 188 ms 21880 KB Output is correct
4 Correct 283 ms 22680 KB Output is correct
5 Correct 899 ms 23032 KB Output is correct
6 Correct 1398 ms 23008 KB Output is correct
7 Correct 620 ms 22816 KB Output is correct
8 Correct 295 ms 22928 KB Output is correct
9 Correct 611 ms 22940 KB Output is correct
10 Correct 2253 ms 22960 KB Output is correct