oj.uz

Submission #98687

# Submission time Handle Problem Language Result Execution time Memory
98687 2019-02-25T04:02:09 Z Mercenary Relativnost (COCI15_relativnost) C++14
0 / 140
 63 ms 20984 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e4 + 7;

int n , c , a[maxn] , b[maxn];
int res = 0;
int q , p;

void enter()
{
    cin >> n >> c;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i];
    for(int i = 1 ; i <= n ; ++i)cin >> b[i];
    cin >> q;
}

int Pow(int a , int b){
    if(b == 0)return 1;
    int r = Pow(a , b / 2);
    if(b & 1)return (ll)r * r % mod * a % mod;
    return (ll)r * r % mod;
}

void add(int & x , int y){
    x += y;
    if(x < 0)x += mod;
    if(x >= mod)x -= mod;
}

struct node{
    vector<int>dp;
    node(){};

}s[maxn * 4];
//20 * maxn * 4 = 8e6

void Merge(node & res , const node & x , const node & other) {
    res.dp.resize(min((int)x.dp.size()+(int)other.dp.size(),c),0);
    for(int i = 0 ; i < res.dp.size() ; ++i)res.dp[i] = 0;
    for(int i = 0 ; i < c ; ++i){
        for(int j = 0 ; j < c - i ; ++j){
            add(res.dp[i + j],(ll)x.dp[i] * other.dp[j] % mod);
        }
    }
}

void build(int x , int l , int r){
    if(l == r){
        s[x].dp.resize(2,0);
        s[x].dp[0] = b[l];
        s[x].dp[1] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(x * 2 , l , mid);
    build(x * 2 + 1 , mid + 1 , r);
    Merge(s[x], s[x * 2],s[x * 2 + 1]);
}

void update(int x , int l , int r){
    if(l == r){
        s[x].dp[0] = b[l];
        s[x].dp[1] = a[l];
        return;
    }
    int mid = l + r >> 1;
    if(mid >= p)update(x * 2 , l , mid);
    else update(x * 2 + 1 , mid + 1 , r);
    Merge(s[x], s[x * 2],s[x * 2 + 1]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    enter();
    build(1,1,n);
//    cout << s[1].dp[0] << endl;
    int res = 1;
    for(int i = 1 ; i <= n ; ++i)res = (ll)res * (a[i] + b[i]) % mod;
    while(q--){
        cin >> p;
        res = (ll)res * Pow(a[p] + b[p],mod-2) % mod;
        cin >> a[p] >> b[p];
        res = (ll)res * (a[p] + b[p]) % mod;
        update(1,1,n);
        int tmpres = res;
        for(int j = 0 ; j < c ; ++j){
            tmpres -= s[1].dp[j];
//            cout << s[1].dp[j] << " ";
            if(tmpres < 0)tmpres += mod;
        }
        cout << tmpres << '\n';
    }
}

Compilation message

relativnost.cpp: In function 'void Merge(node&, const node&, const node&)':
relativnost.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < res.dp.size() ; ++i)res.dp[i] = 0;
                     ~~^~~~~~~~~~~~~~~
relativnost.cpp: In function 'void build(int, int, int)':
relativnost.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
relativnost.cpp: In function 'void update(int, int, int)':
relativnost.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:83:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
relativnost.cpp:83:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 28 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 35 ms 19576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 46 ms 20088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 42 ms 20860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 49 ms 20984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 52 ms 20472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 63 ms 20956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 45 ms 20728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 43 ms 20600 KB Execution killed with signal 11 (could be triggered by violating memory limits)