Submission #98582

#	Time	Username	Problem	Language	Result	Execution time	Memory
98582		JohnTitor	Relativnost (COCI15_relativnost)	C++11	140 / 140	957 ms	24404 KiB

relativnost

#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 / 140