oj.uz

Submission #398297

# Submission time Handle Problem Language Result Execution time Memory
398297 2021-05-04T06:36:49 Z Mazaalai Strange Device (APIO19_strange_device) C++14
10 / 100
 5000 ms 524292 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
// #define FOR(i, begin, end) for (__typeof(end) i = (begin); i != (end) + 1 - 2 * ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORB(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a) for (int i = 0; i < a; i++)
#define REP1(i, a) for (int i = 1; i < a; i++)
#define REPB(i, a) for (int i = a - 1; i >= 0; i--)
#define TRAV(a,x) for (auto& a: x)
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define II <int, int>
#define Q queue
#define ff first
#define bk back()
#define ss second
#define rs resize
#define ins insert 
#define fr front() 
#define ts to_string
#define pb push_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound 
#define PQ priority_queue
#define umap unordered_map
#define sz(x) (int)x.size()

typedef long long ll;
typedef double db;
typedef unsigned uint;
typedef unsigned long long ull;
typedef unordered_map<int, int> umapII;
// PQ going up <int, VI, greater<int> >
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<VVB> VVVB;
typedef vector<umapII> VumapII;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<VVLL> VVVLL;
typedef vector<VVVLL> VVVVLL;
typedef vector<db> VD;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<PII> VPI;
typedef vector<VPI> VVPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VVVI> VVVVI;
typedef vector<VVVVI> VVVVVI;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void eraseDups(VI& a) {
    a.erase(unique(a.begin(), a.end()), a.end());
}
int strToInt(string&a) {
    stringstream x(a);
    int b;
    x >> b;
    return b;
}
void readI(int& a) {
    cin >> a;
}
void readI(int& a, int&b) {
    cin >> a >> b;
}
void readI(int& a, int&b, int&c) {
    cin >> a >> b >> c;
}
VI readVI(int n) {
    VI a(n);
    REP(i, n) cin >> a[i];
    return a;
}
VVI readVVI(int n, int m) {
    VVI a(n, VI(m));
    REP(i, n) a[i] = readVI(m);
    return a;
}
VLL readVLL(ll n) {
    VLL a(n);
    REP(i, n) cin >> a[i];
    return a;
}
VVLL readVVLL(ll n, ll m) {
    VVLL a(n, VLL(m));
    REP(i, n) a[i] = readVLL(m);
    return a;
}


int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}

void print(VI& a) {
    for (auto el : a) {
        cout << el << ' ';
    }
    cout << '\n';
}

void print(VI& a, int n) {
    int cnt = 0;
    for (auto el : a) {
        if (cnt++ == n) break;
        cout << el << ' ';
    }
    cout << '\n';
}
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;//119*2^23 +1;
const int INF = 2e9;
const ll INFF = INT64_MAX;
const db EPS = 1e-9;
const db PI = acos(-1.0); //M_PI;
const int moveX[] = {-1, 0, 1, 0};
const int moveY[] = {0, 1, 0, -1};
/*
|      ⣠⣶⡾⠏⠉⠙⠳⢦⡀⠀  ⠀⢠⠞⠉⠙⠲⡀
|    ⣴⠿⠏⠀⠀⠀⠀⠀⠀⢳⡀⠀  ⡏⠀⠀ ⠀⠀ ⢷
|⠀⠀⢠⣟⣋⡀⢀⣀⣀⡀⠀⣀⡀⣧⠀  ⢸⠀⠀⠀⠀   ⡇ ⠀
| ⠀⢸⣯⡭⠁⠸⣛⣟⠆⡴⣻⡲⣿   ⣸⠀⠀OK.  ⡇
|⠀⠀⣟⣿⡭⠀⠀⠀⠀⠀⢱⠀⠀⣿   ⢹⠀⠀⠀⠀⠀ ⡇
|⠀⠀⠙⢿⣯⠄⠀⠀⠀⢀⡀⠀⠀⡿⠀  ⡇⠀⠀ ⠀ ⡼
|⠀⠀⠀⠀⠹⣶⠆⠀⠀⠀⠀⠀⡴⠃ ⠀ ⠘⠤⣄⣠⠞⠀ ⠀
|⠀⠀⠀⠀⢸⣷⡦⢤⡤⢤⣞⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀
|⠀⢀⣤⣴⣿⣏⠁⠀⠀⠸⣏⢯⣷⣖⣦⡀⠀⠀⠀⠀⠀⠀
|⢀⣾⣽⣿⣿⣿⣿⠛⢲⣶⣾⢉⡷⣿⣿⠵⣿⠀⠀⠀⠀⠀
|⣼⣿⠍⠉⣿⡭⠉⠙⢺⣇⣼⡏⠀ ⠀⣄⢸⣿
|⣿⣿⣧⣀⣿.........⣀⣰⣏⣘⣆⣀
      
|                                                   _         _   _
|                                                   (_)       | | | |
 _ __  _ __ ___   __ _ _ __ __ _ _ __ ___  _ __ ___  _ ___ ___| |_| |_
| '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|
| |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_
| .__/|_|  \___/ \__, |_|  \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|
| |               __/ |
|_|              |___/
 _   _      _ _    __        __         _     _ 
| | | | ___| | | __\ \      / /__  _ __| | __| |
| |_| |/ _ \ | |/ _ \ \ /\ / / _ \| '__| |/ _` |
|  _  |  __/ | | (_) \ V  V / (_) | |  | | (_| |
|_| |_|\___|_|_|\___/ \_/\_/ \___/|_|  |_|\__,_|                                  
 ____     __    _______    _______   __________
|     \  |  |  |  _____|  /  _____) |____  ____|
|  |\  \ |  |  | |__     (  (_____      |  |
|  | \  \|  |  |  __|     \_____  \     |  | 
|  |  \     |  | |_____    _____)  )    |  | 
|__|   \____|  |_______|  (_______/     |__| 
 
 
 


*/












int n, A, B;
void go () {
    cin >> n >> A >> B;
    set <pair <int,int> >seen;
    REP(i, n) {
        int l, r;
        cin >> l >> r;

		for (int i = l; i <= r; i++) {
			// cout << i << ": " << (i + (i / m))%n << ',' << i % m << '\n';
			seen.insert({(i + (i / B))%A, i%B});
		}
    }
    
    cout << seen.size() << '\n';
}



signed main () {

#ifdef ONLINE_JUDGE
#else
    // freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
    _upgrade
    int T = 1;
    while(T--) go();
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
    
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 12268 KB Output is correct
3 Correct 72 ms 17884 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 8 ms 1100 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 42 ms 6940 KB Output is correct
16 Correct 29 ms 7104 KB Output is correct
17 Correct 63 ms 10212 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 2900 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 140 ms 32212 KB Output is correct
3 Correct 189 ms 31972 KB Output is correct
4 Correct 129 ms 30692 KB Output is correct
5 Execution timed out 5093 ms 62520 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 590 ms 63616 KB Output is correct
3 Runtime error 2168 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 590 ms 63616 KB Output is correct
3 Runtime error 2168 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 590 ms 63616 KB Output is correct
3 Runtime error 2168 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Runtime error 1662 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 12268 KB Output is correct
3 Correct 72 ms 17884 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 8 ms 1100 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 42 ms 6940 KB Output is correct
16 Correct 29 ms 7104 KB Output is correct
17 Correct 63 ms 10212 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Runtime error 2900 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -