/**
<=================================================================>
{ *Author:Le Son-Tk2cht }
{ *Spawn:01/10/2006-Ha Tinh City-VN }
{ *School:Ha Tinh High School for the Gifted }
{ (\_/) <----------------------------------> }
{ (•_•) {|Written by LeSonnn-SharkLord-Tk2|} }
{ />💻 <----------------------------------> }
{ }
{ ________________________________ }
{ / (Code) / (Debug) / }
{ /===============================/ }
{ <------------(Choose)------------> }
{ Goal:... }
<=================================================================>
It's never too late to start over
If you're not happy with yesterday,try something different today
Don't stay stuck
Do better
**/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<unordered_map>
#include<queue>
#define task"relativnost"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long llu;
typedef pair<long long,long long>ii;
typedef tree<int,null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//fastio
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define file_inp(_s_) freopen((_s_).c_str(), "r", stdin)
#define file_out(_s_) freopen((_s_).c_str(), "w", stdout)
#pragma GCC optimize ("Ofast")
//struct-----pair
#define mp make_pair
#define fi first
#define se second
//vector
#define pb push_back
#define pf push_front
#define eb emplace_back
#define sz(a) (int)(a.size())
//bit
#define bp __builtin_popcount
#define mask(a) (1LL<<(a))
#define readbit(a,x) ((a>>x)&1)
//loops
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOD(i,a,b) for(int i=a;i>=b;i--)
#define FORA(i,a,b) for(int i=a;i<b;i++)
#define FORB(i,a,b) for(int i=a-1;i>=b;i--)
#define REP(a,x) for(auto& a:x)
//endl-----'\n'
#define EL cout<<'\n'
#define ELE cout<<endl
//fast cin-cout
inline int ReadInt()
{
char ktn;
for(ktn=getchar();ktn<'0'||ktn>'9';ktn=getchar());
int mla=ktn-'0';
for(ktn=getchar();ktn>='0'&&ktn<='9';ktn=getchar())
mla=mla*10+ktn-'0';
return mla;
}
void WriteInt(int mla)
{
if(mla>9) WriteInt(mla/10);
putchar(mla%10+'0');
}
//mazimize-minimize
template<class shark>
inline bool minimize(shark &a,const shark &b)
{
return (a > b ? (a = b),1 : 0);
}
template<class shark>
inline bool maximize(shark &a,const shark &b)
{
return (a < b ? (a = b),1 : 0);
}
template<typename shark>
bool to_maximize(shark &x, const shark &y)
{
if(x<y)
{
x=y;
return true;
}
return false;
}
//fast bp,bit,lcm
long long bpow(long long n,long long m,long long mod)
{
long long res=1;while(m){if(m&1)res=res*n%mod;n=n*n%mod;m>>=1;}
return res;
}
long long getbit(long long val,long long num)
{
return ((val>>num)*1LL);
}
long long lcm(long long a,long long b)
{
return a*b/__gcd(a,b);
}
//===============================================>>
void file(const string FILE="Test")
{
freopen((FILE+".INP").c_str(),"r",stdin);
freopen((FILE+".OUT").c_str(),"w",stdout);
}
//declare
const int MOD=1e4+7;
class Node
{
public:
int dp[21];
bool id;
Node (bool id)
{
this->id = id;
FORA(i,0,21)
{
dp[i] = 0;
}
}
};
Node merge (Node n1, Node n2)
{
if (!n1.id) return n2;
if (!n2.id) return n1;
Node ans(true);
FORA(i,0,21)
{
FORA(j,0,21)
{
ans.dp[min(i + j, 20)] += (n1.dp[j] * n2.dp[i]) % MOD;
}
}
FORA(i,0,21)
{
ans.dp[i] %= MOD;
}
return ans;
}
Node get_node (pair<int,int> p)
{
Node ans(true);
ans.dp[0] = p.se;
ans.dp[1] = p.fi;
return ans;
}
template<class T>
class SegmentTree
{
public:
SegmentTree (int N)
{
N = (1 << ((int)floor(log2(N - 1)) + 1));
this->N = N;
val.assign(2 * N, Node(false));
}
void update (int x, T y)
{
x += N - 1;
val[x] = y;
while (x != 0) {
x = (x - 1)/2;
val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
}
}
vector<T> val;
private:
int N;
};
void solve()
{
int N, C;
cin >> N >> C;
SegmentTree<Node> st(N);
vector<int> x(N), y(N);
FORA(i,0,N)
{
cin >> x[i];
}
FORA(i,0,N)
{
cin >> y[i];
}
FORA(i,0,N)
{
x[i] %= MOD, y[i] %= MOD;
st.update(i, get_node({x[i], y[i]}));
}
int Q;
cin >> Q;
while (Q--)
{
int ind, a, b;
cin >> ind >> a >> b;
a %= MOD, b %= MOD;
ind--;
st.update(ind, get_node({a, b}));
int64_t ans = 0;
FOR(i,C,20)
{
ans += st.val[0].dp[i];
}
cout << ans % MOD << '\n';
}
}
//main
int main()
{
//Written by LeSonnn_
fast
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ll nt;
for(nt=1;nt--;)
{
solve();
}
}
/**
Input:
okokok
Output:
kokoko
**/
Compilation message
relativnost.cpp:25:9: warning: ISO C++11 requires whitespace after the macro name
25 | #define task"relativnost"
| ^~~~
relativnost.cpp: In function 'void file(std::string)':
relativnost.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen((FILE+".INP").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:115:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | freopen((FILE+".OUT").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
226 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:227:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
227 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
528 KB |
Output is correct |
| 2 |
Correct |
19 ms |
540 KB |
Output is correct |
| 3 |
Correct |
16 ms |
536 KB |
Output is correct |
| 4 |
Correct |
1408 ms |
14956 KB |
Output is correct |
| 5 |
Correct |
1959 ms |
27668 KB |
Output is correct |
| 6 |
Correct |
1808 ms |
27300 KB |
Output is correct |
| 7 |
Correct |
1445 ms |
15100 KB |
Output is correct |
| 8 |
Correct |
1636 ms |
26840 KB |
Output is correct |
| 9 |
Correct |
2111 ms |
27764 KB |
Output is correct |
| 10 |
Correct |
2092 ms |
27692 KB |
Output is correct |
