| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 597832 | LeSonnn | Relativnost (COCI15_relativnost) | C++17 | 2111 ms | 27764 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
<=================================================================>
{ *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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||