oj.uz

답안 #371260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371260 2021-02-26T10:08:28 Z Atill83 Relativnost (COCI15_relativnost) C++14
42 / 140
 3892 ms 23188 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e4+7;
const int MAXN = (int) 1e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, c;
int a[MAXN], b[MAXN];


int t[4*MAXN][21];

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v][0] = b[tl];
        t[v][1] = a[tl];
    }else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v + 1, tm + 1, tr);
        for(int j = 0; j <= c; j++)
            t[v][j] = 0;
        for(int i = 0; i <= c; i++){
            for(int j = 0; j <= c; j++){
                t[v][min(c, (i + j))] = (t[v][min(c, (i + j))] + t[2*v][i] * t[2*v + 1][j] % mod) % mod;
            }
        }
    }
}

void upd(int v, int tl, int tr, int pos){
    if(tl == tr){
        t[v][0] = b[tl];
        t[v][1] = a[tl];
    }else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(2*v, tl, tm, pos);
        else
            upd(2*v + 1, tm + 1, tr, pos);
        for(int j = 0; j <= c; j++)
            t[v][j] = 0;
        for(int i = 0; i <= c; i++){
            for(int j = 0; j <= c; j++){
                t[v][min(c, (i + j))] = (t[v][min(c, (i + j))] + t[2*v][i] * t[2*v + 1][j] % mod) % mod;
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>c;

    for(int i = 0; i < n; i++){
        cin>>a[i];   
        a[i] % mod;
    }
    for(int i = 0; i < n; i++){
        cin>>b[i];
        b[i] %= mod;
    }
    
    build(1, 0, n - 1);
 
    int q;
    cin>>q;

    for(int i = 0; i < q; i++){
        int idx;
        cin>>idx;
        idx--;
        cin>>a[idx]>>b[idx];
        a[idx] %= mod;
        b[idx] %= mod;
        upd(1, 0, n - 1, idx);
        cout<<t[1][c]<<endl;
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:72:14: warning: statement has no effect [-Wunused-value]
   72 |         a[i] % mod;
      |         ~~~~~^~~~~

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 492 KB Output is correct
2 Correct 14 ms 492 KB Output is correct
3 Correct 28 ms 492 KB Output is correct
4 Incorrect 501 ms 12060 KB Output isn't correct
5 Incorrect 1698 ms 23020 KB Output isn't correct
6 Incorrect 2448 ms 22996 KB Output isn't correct
7 Incorrect 1056 ms 12036 KB Output isn't correct
8 Incorrect 538 ms 22764 KB Output isn't correct
9 Incorrect 1012 ms 23140 KB Output isn't correct
10 Incorrect 3892 ms 23188 KB Output isn't correct