oj.uz

Submission #1092013

# Submission time Handle Problem Language Result Execution time Memory
1092013 2024-09-22T21:12:31 Z DeathIsAwe Toll (BOI17_toll) C++17
7 / 100
 56 ms 40792 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int segment[131072];


void add(int pos, int a) {
    pos += 65536;
    segment[pos] = a;
    pos /= 2;
    while (pos > 0) {
        if (segment[2*pos + 1] == -1 || segment[2*pos] == -1) {
            segment[pos] = -1;
        } else {
            segment[pos] = segment[2*pos + 1] + segment[2*pos];
        }
        pos /= 2;
    }
}


int find(int a, int b) {
    a += 65536; b += 65536 - 1;
    int val = 0;
    while (a <= b) {
        if (a % 2 == 1) {
            if (segment[a] == -1) {
                val = -1; break;
            }
            val += segment[a++];
        }
        if (b % 2 == 0) {
            if (segment[b] == -1) {
                val = -1; break;
            }
            val += segment[b--];
        }
        a /= 2; b /= 2;
    }
    if (val == 0) {
        return -1;
    }
    return val;
}


int main() {
    int k, n, m, o, d1, d2, t; cin >> k >> n >> m >> o;
    if (k == 1) {
        for (int i=0;i<131072;i++) {
            segment[i] = -1;
        }
        for (int i=0;i<m;i++) {
            cin >> d1 >> d2 >> t;
            add(d1, t);
        }
        for (int i=0;i<o;i++) {
            cin >> d1 >> d2;
            cout << find(d1, d2) << '\n';
        }
    }
    int graph[(n + k - 1) / k][k][51][k];
    for (int i=0;i<n+k-1;i++) {
        for (int j=0;j<k;j++) {
            for (int x=0;x<50;x++) {
                for (int y=0;y<k;y++) {
                    graph[i][j][x][y] = 0;
                }
            }
        }
    }
    for (int i=0;i<m;i++) {
        cin >> d1 >> d2 >> t;
        graph[d1/k][d1%k][1][d2%k] = t;
    }
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:63:9: warning: variable 'graph' set but not used [-Wunused-but-set-variable]
   63 |     int graph[(n + k - 1) / k][k][51][k];
      |         ^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10836 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 968 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 55 ms 11604 KB Output is correct
9 Correct 53 ms 11796 KB Output is correct
10 Correct 27 ms 10840 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 40792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 860 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 860 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10836 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 968 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 55 ms 11604 KB Output is correct
9 Correct 53 ms 11796 KB Output is correct
10 Correct 27 ms 10840 KB Output is correct
11 Runtime error 29 ms 40792 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -