oj.uz

Submission #477809

# Submission time Handle Problem Language Result Execution time Memory
477809 2021-10-04T01:32:43 Z sumit_kk10 Modsum (NOI12_modsum) C++14
25 / 25
 142 ms 464 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int MOD = 5;
const int N = 1e7 + 5;
int n, v[N], w[N];
vector<int> vv;
long long ans;

ll power(ll x, ll y){
    x %= MOD;
    ll ans = 1;
    while(y){
        if(y & 1)
            ans = (ans * x) % MOD;
        y >>= 1LL;
        x = (x * x) % MOD;
    }
    return ans;
}

int calc(){
	long long int sum = 0;
	for(auto k : vv)
		sum += k;
	long long ok = power(sum, 4);
	ok = (ok % 5);
	ok += 2 * (power(sum, 2));
	ok = (ok % 5);
	return (ok + 1);
}

void go(int i){
	if(i == n + 1){
		ans += calc();
		return;
	}
	for(int j = v[i]; j <= w[i]; ++j){
		vv.push_back(j);
		go(i + 1);
		vv.pop_back();
	}
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> v[i] >> w[i];
	go(1);
	cout << ans << '\n';
}

int main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 324 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 2 ms 336 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 6 ms 208 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 6 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 18 ms 340 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 464 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 115 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 142 ms 400 KB Output is correct