oj.uz

Submission #741944

# Submission time Handle Problem Language Result Execution time Memory
741944 2023-05-15T06:22:47 Z vjudge1 Boat (APIO16_boat) C++17
31 / 100
 2000 ms 303040 KB 
// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")  
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int K = 800;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 100;

int n, sz;
int a[maxn];
int b[maxn];
int t[maxn*4];
int dp[maxn];
map<int, int>cnt;

int add(int a, int b){
    return (a+b)%mod;
}

void upd(int x, int y, int v=1, int tl=1, int tr=sz){
    if(tl == tr) t[v] = add(t[v], y);
    else{
        int tm = (tl+tr)>>1;
        if(x <= tm) upd(x, y, v<<1, tl, tm);
        else upd(x, y, (v<<1)+1, tm+1, tr);
        t[v] = add(t[v<<1], t[(v<<1)+1]);
    } 
}

int get(int r, int v=1, int tl=1, int tr=sz){
    if(r < tl) return 0;
    if(tr <= r) return t[v];
    int tm = (tl+tr)>>1;
    return add(get(r, v<<1, tl, tm), get(r, (v<<1)+1, tm+1, tr));
}

void IHTW(){
    cin >> n;
    int ans = 0;
    set<int>st;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
        for(int j=a[i]; j<=b[i]; j++) st.insert(j);
    }
    for(auto to: st) cnt[to] = ++sz;
    for(int i=1; i<=n; i++){
        for(int j=b[i]; j>=a[i]; j--){
            int x = cnt[j];
            int nw = add(get(x-1), 1);
            upd(x, nw);
            ans = add(ans, nw);
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t=1;
    while(t--) IHTW();
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 220 ms 888 KB Output is correct
22 Correct 231 ms 844 KB Output is correct
23 Correct 211 ms 892 KB Output is correct
24 Correct 229 ms 844 KB Output is correct
25 Correct 239 ms 892 KB Output is correct
26 Correct 230 ms 780 KB Output is correct
27 Correct 240 ms 844 KB Output is correct
28 Correct 228 ms 724 KB Output is correct
29 Correct 251 ms 724 KB Output is correct
30 Correct 841 ms 101384 KB Output is correct
31 Correct 836 ms 99692 KB Output is correct
32 Correct 870 ms 101548 KB Output is correct
33 Correct 846 ms 98980 KB Output is correct
34 Correct 861 ms 99864 KB Output is correct
35 Correct 763 ms 95628 KB Output is correct
36 Correct 791 ms 98744 KB Output is correct
37 Correct 808 ms 99632 KB Output is correct
38 Correct 778 ms 96832 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 303040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 220 ms 888 KB Output is correct
22 Correct 231 ms 844 KB Output is correct
23 Correct 211 ms 892 KB Output is correct
24 Correct 229 ms 844 KB Output is correct
25 Correct 239 ms 892 KB Output is correct
26 Correct 230 ms 780 KB Output is correct
27 Correct 240 ms 844 KB Output is correct
28 Correct 228 ms 724 KB Output is correct
29 Correct 251 ms 724 KB Output is correct
30 Correct 841 ms 101384 KB Output is correct
31 Correct 836 ms 99692 KB Output is correct
32 Correct 870 ms 101548 KB Output is correct
33 Correct 846 ms 98980 KB Output is correct
34 Correct 861 ms 99864 KB Output is correct
35 Correct 763 ms 95628 KB Output is correct
36 Correct 791 ms 98744 KB Output is correct
37 Correct 808 ms 99632 KB Output is correct
38 Correct 778 ms 96832 KB Output is correct
39 Execution timed out 2076 ms 303040 KB Time limit exceeded
40 Halted 0 ms 0 KB -