oj.uz

Submission #469162

# Submission time Handle Problem Language Result Execution time Memory
469162 2021-08-31T03:17:10 Z Cross_Ratio Strange Device (APIO19_strange_device) C++14
35 / 100
 1043 ms 48364 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    if(a < b) swap(a, b);
    while(b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
vector<int> B;
int getidx(int n) {
    return lower_bound(B.begin(),B.end(),n) - B.begin();
}
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=2;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = seg[2*n] + seg[2*n+1];
            n /= 2;
        }
    }
    void Plus(int n) {
        seg[n+MAX/2]++;
        update(n);
    }
    void Minus(int n) {
        seg[n+MAX/2]--;
        update(n);
    }
    int sum(int s, int e) {
        return sum(s, e, 1, 0, MAX/2);
    }
};
int L[1000005];
int R[1000005];
main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, a, b;
    cin >> N >> a >> b;
    int d = gcd(a, b + 1);
    int c = a / d;
    assert(a % d == 0);
    int k = b * c;
    int l, r;
    bool isAll = false;
    int i;
    B.push_back(0);
    B.push_back(k);
    for(i=0;i<N;i++) {
        cin >> L[i] >> R[i];
        if(R[i] - L[i] >= k) isAll = true;
        L[i] %= k;
        R[i] %= k;
        R[i]++;
        B.push_back(L[i]);
        B.push_back(R[i]);
    }
    sort(B.begin(),B.end());
    B.erase(unique(B.begin(),B.end()),B.end());
    SegTree tree(B.size() + 10);
    for(i=0;i<N;i++) {
        int l = getidx(L[i]);
        int r = getidx(R[i]);
        if(l < r) {
            tree.Plus(l);
            tree.Minus(r);
        }
        else {
            tree.Plus(0);
            tree.Minus(r);
            tree.Plus(l);
            tree.Minus(B.size()-1);
        }
    }
    int cnt = 0;
    for(i=0;i<B.size()-1;i++) {
        if(tree.sum(0,i+1)!=0) {
            cnt += B[i+1]-B[i];
        }
    }
    cnt = isAll ? k : cnt;
    cout << cnt;
}

Compilation message

strange_device.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
strange_device.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
strange_device.cpp: At global scope:
strange_device.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:97:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(i=0;i<B.size()-1;i++) {
      |             ~^~~~~~~~~~~
strange_device.cpp:65:9: warning: unused variable 'l' [-Wunused-variable]
   65 |     int l, r;
      |         ^
strange_device.cpp:65:12: warning: unused variable 'r' [-Wunused-variable]
   65 |     int l, r;
      |            ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 11 ms 1016 KB Output is correct
3 Correct 9 ms 976 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 8 ms 976 KB Output is correct
17 Correct 90 ms 5640 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 432 ms 31836 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 920 ms 48080 KB Output is correct
3 Correct 959 ms 48168 KB Output is correct
4 Correct 1043 ms 48136 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 920 ms 48080 KB Output is correct
3 Correct 959 ms 48168 KB Output is correct
4 Correct 1043 ms 48136 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 889 ms 48168 KB Output is correct
7 Correct 883 ms 48332 KB Output is correct
8 Correct 916 ms 48140 KB Output is correct
9 Correct 1037 ms 48132 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 920 ms 48080 KB Output is correct
3 Correct 959 ms 48168 KB Output is correct
4 Correct 1043 ms 48136 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 85 ms 5748 KB Output is correct
7 Correct 90 ms 5536 KB Output is correct
8 Correct 86 ms 5688 KB Output is correct
9 Correct 87 ms 5568 KB Output is correct
10 Correct 87 ms 5564 KB Output is correct
11 Correct 88 ms 5576 KB Output is correct
12 Correct 87 ms 5640 KB Output is correct
13 Correct 91 ms 5520 KB Output is correct
14 Correct 103 ms 5556 KB Output is correct
15 Correct 89 ms 5636 KB Output is correct
16 Correct 92 ms 5644 KB Output is correct
17 Correct 87 ms 5744 KB Output is correct
18 Correct 916 ms 48260 KB Output is correct
19 Correct 950 ms 48364 KB Output is correct
20 Correct 985 ms 48180 KB Output is correct
21 Correct 110 ms 5640 KB Output is correct
22 Correct 84 ms 5532 KB Output is correct
23 Correct 174 ms 12756 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 95 ms 5632 KB Output is correct
3 Correct 106 ms 5596 KB Output is correct
4 Correct 1000 ms 48172 KB Output is correct
5 Correct 93 ms 5564 KB Output is correct
6 Correct 91 ms 5648 KB Output is correct
7 Correct 106 ms 5616 KB Output is correct
8 Correct 102 ms 5540 KB Output is correct
9 Correct 90 ms 5640 KB Output is correct
10 Correct 91 ms 5644 KB Output is correct
11 Correct 96 ms 5580 KB Output is correct
12 Correct 84 ms 5580 KB Output is correct
13 Correct 93 ms 5632 KB Output is correct
14 Correct 986 ms 48328 KB Output is correct
15 Correct 98 ms 5616 KB Output is correct
16 Correct 905 ms 48292 KB Output is correct
17 Correct 916 ms 48228 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 11 ms 1016 KB Output is correct
3 Correct 9 ms 976 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 8 ms 976 KB Output is correct
17 Correct 90 ms 5640 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct