oj.uz

답안 #98582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98582 2019-02-24T15:20:14 Z JohnTitor Relativnost (COCI15_relativnost) C++11
140 / 140
 957 ms 24404 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "RELATIVNOST"
///https://oj.uz/problem/view/COCI15_relativnost
int n, k;
const int base=10007;
class segment_tree{
public:
    using pointer=segment_tree*;
    pointer left, right;
    int f[20];
    int all;
    int l, r, m;
    segment_tree(int l, int r){
        this->l=l;
        this->r=r;
        m=(l+r)/2;
        FFOR(i, 0, k) f[i]=0;
        if(l!=r){
            left=new segment_tree(l, m);
            right=new segment_tree(m+1, r);
        }
    }
    void update(int u, int a, int b){
        if(l==r){
            f[1]=a%base;
            f[0]=b%base;
            all=(a+b)%base;
        }
        else{
            if(m>=u) left->update(u, a, b);
            else right->update(u, a, b);
            all=(left->all*right->all)%base;
            FFOR(i, 0, k) f[i]=0;
            FFOR(i, 0, k) if(left->f[i]) FFOR(j, 0, k-i) if(right->f[j]) f[i+j]+=left->f[i]*right->f[j];
            FFOR(i, 0, k) f[i]%=base;
        }
    }
    int get(){
        int res=all;
        FFOR(i, 0, k) res-=f[i];
        res%=base;
        if(res<0) res+=base;
        return res;
    }
};
segment_tree::pointer tree;
int a[100001];
int b[100001];
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    read(n);
    read(k);
    FOR(i, 1, n) read(a[i]);
    FOR(i, 1, n) read(b[i]);
    tree=new segment_tree(1, n);
    FOR(i, 1, n) tree->update(i, a[i], b[i]);
    {
        int q, u, a, b;
        read(q);
        FOR(i, 1, q){
            read(u);
            read(a);
            read(b);
            tree->update(u, a, b);
            writeln(tree->get());
        }
    }
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 10 ms 512 KB Output is correct
4 Correct 269 ms 14176 KB Output is correct
5 Correct 503 ms 23104 KB Output is correct
6 Correct 736 ms 24404 KB Output is correct
7 Correct 428 ms 16924 KB Output is correct
8 Correct 294 ms 23800 KB Output is correct
9 Correct 427 ms 19832 KB Output is correct
10 Correct 957 ms 19292 KB Output is correct