oj.uz

Submission #167331

# Submission time Handle Problem Language Result Execution time Memory
167331 2019-12-07T12:00:16 Z Atill83 Segway (COI19_segway) C++14
100 / 100
 363 ms 26488 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
bool acc[305];
int sure[305][MAXN];
int open[MAXN];
int seg[MAXN][3];
int tree[MAXN];

void upd(int yer){
    for(; yer <= 15000; yer += (yer&-yer)){
        tree[yer]++;
    }
}

int get(int yer){
    int res = 0;
    for(; yer > 0; yer -= (yer&-yer)) res += tree[yer];
    return res;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n;

    for(int i = 0; i < n; i++){
        cin>>seg[i][0]>>seg[i][1]>>seg[i][2];
    }
    int m;
    cin>>m;
    for(int i = 0; i < m; i++){
        int yer;
        cin>>yer;
        acc[yer] = 1;
    }
    for(int i = 0; i < 300; i++){
        int wc = (i < 100 ? 0 : (i < 200 ? 1 : 2));
        for(int j = 0; j < n; j++){
            if(open[j]){
                open[j]--;
                sure[i + 1][j] = sure[i][j] + 1;
            }else{
                if(acc[i]){
                    open[j] = (get(sure[i][j] - 1))%20;
                    //cout<<i<<" "<<j<<" "<<open[j]<<endl;
                    if(open[j]){
                        open[j]--;
                        sure[i + 1][j] = sure[i][j] + 1;
                    }else{
                        sure[i + 1][j] = sure[i][j] + seg[j][wc];
                    }
                }else{
                    sure[i + 1][j] = sure[i][j] + seg[j][wc];
                }
            }
        }
        for(int j = 0; j < 15005; j++){
            tree[j] = 0;
        }
        for(int j = 0; j < n; j++){
            upd(sure[i + 1][j]);
        }
    }
    for(int i = 0; i < n; i++){
        cout<<sure[300][i]<<endl;
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 7 ms 2552 KB Output is correct
3 Correct 12 ms 3292 KB Output is correct
4 Correct 31 ms 5880 KB Output is correct
5 Correct 363 ms 26232 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 6 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 6 ms 2296 KB Output is correct
5 Correct 6 ms 2296 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Correct 7 ms 2424 KB Output is correct
8 Correct 8 ms 2552 KB Output is correct
9 Correct 8 ms 2552 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Correct 9 ms 2680 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 7 ms 2552 KB Output is correct
3 Correct 12 ms 3292 KB Output is correct
4 Correct 31 ms 5880 KB Output is correct
5 Correct 363 ms 26232 KB Output is correct
6 Correct 6 ms 2296 KB Output is correct
7 Correct 6 ms 2296 KB Output is correct
8 Correct 6 ms 2296 KB Output is correct
9 Correct 6 ms 2296 KB Output is correct
10 Correct 6 ms 2296 KB Output is correct
11 Correct 6 ms 2424 KB Output is correct
12 Correct 7 ms 2424 KB Output is correct
13 Correct 8 ms 2552 KB Output is correct
14 Correct 8 ms 2552 KB Output is correct
15 Correct 9 ms 2680 KB Output is correct
16 Correct 9 ms 2680 KB Output is correct
17 Correct 15 ms 3568 KB Output is correct
18 Correct 26 ms 4728 KB Output is correct
19 Correct 93 ms 12928 KB Output is correct
20 Correct 105 ms 15608 KB Output is correct
21 Correct 150 ms 20472 KB Output is correct
22 Correct 199 ms 26488 KB Output is correct
23 Correct 198 ms 26372 KB Output is correct