Submission #847917

#TimeUsernameProblemLanguageResultExecution timeMemory
847917TB_Relativnost (COCI15_relativnost)C++17
0 / 140
1102 ms33700 KiB
#include <bits/stdc++.h> using namespace std; // #undef _GLIBCXX_DEBUG // disable run-time bound checking, etc // #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens // #pragma GCC optimize ("unroll-loops") // #pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation // #pragma GCC target("movbe") // byte swap // #pragma GCC target("aes,pclmul,rdrnd") // encryption // #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD // #include <bits/extc++.h> // using namespace __gnu_pbds; // template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; // template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>; #define ll long long #define INF (ll)1e9+7 #define fo(i, n) for(ll i=0;i<((ll)n);i++) #define deb(x) cout << #x << " = " << x << endl; #define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl #define pb push_back #define mp make_pair #define F first #define S second #define LSOne(S) ((S) & (-S)) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; } inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; } inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; } template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds> auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);} typedef pair<int, int> pii; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpii; typedef vector<pl> vpl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<vpii> vvpii; typedef vector<vpl> vvpl; ll n, c; vpl vals; struct Node{ Node *lnode, *rnode; int l, r; vi scores; Node(int l, int r) : l(l), r(r) { scores.assign(25, 0); if(r-l == 1) { scores[0] = vals[l].S; scores[1] = vals[l].F; }else{ int mid = (l+r) / 2; lnode = new Node(l, mid); rnode = new Node(mid, r); fo(i, c+1){ fo(j, c+1){ scores[min(c, i+j)] += lnode->scores[i]*rnode->scores[j]; } } fo(i, c+1) scores[i] = scores[i]%10007; } } void update(int lo, int hi){ if(r <= lo || hi <= l) return; if(r-l == 1){ scores[0] = vals[l].S; scores[1] = vals[l].F; return; } lnode->update(lo, hi); rnode->update(lo, hi); fo(i, c+1) scores[i] = 0; fo(i, c+1){ fo(j, c+1){ scores[min(c, i+j)] += lnode->scores[i]*rnode->scores[j]; } } fo(i, c+1) scores[i] = scores[i]%10007; } }; int main() { // cout << fixed << setprecision(20); // auto start = std::chrono::steady_clock::now(); // since(start).count() cin.tie(0)->sync_with_stdio(0); cin >> n >> c; int newpos, val1, val2, q; fo(i, n){ cin >> val1; vals.pb({val1%10007, 0}); } fo(i, n){ cin >> vals[i].S; vals[i].S = vals[i].S%10007; } cin >> q; Node st(0, n); while(q--){ cin >> newpos >> val1 >> val2; vals[newpos-1] = mp(val1, val2); st.update(newpos-1, newpos); cout << st.scores[c] << "\n"; } exit(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...