oj.uz

Submission #785876

# Submission time Handle Problem Language Result Execution time Memory
785876 2023-07-17T17:30:58 Z Andrey Digital Circuit (IOI22_circuit) C++17
16 / 100
 1406 ms 2097152 KB 
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;

vector<long long> dp(300001);
vector<long long> bruh(300001);
vector<long long> br(300001);
vector<long long> f(300001);
long long p2[300001];
long long n,m;
const long long MOD = 1e9+2022;

void upd(long long l, long long r, long long x, long long nl, long long nr) {
    if(l == nl && r == nr) {
        f[x]++;
        return;
    }
    long long m = (nl+nr)/2;
    if(r <= m) {
        upd(l,r,x*2+1,nl,m);
    }
    else if(l > m) {
        upd(l,r,x*2+2,m+1,nr);
    }
    else {
        upd(l,m,x*2+1,nl,m);
        upd(m+1,r,x*2+2,m+1,nr);
    }
    long long a = dp[x*2+1],b = dp[x*2+2];
    if(f[x*2+1]%2) {
        a = (p2[br[x*2+1]]-a+MOD)%MOD;
    }
    if(f[x*2+2]%2) {
        b = (p2[br[x*2+2]]-b+MOD)%MOD;
    }
    dp[x] = (p2[br[x*2+1]]*(a+b))%MOD;
}

void build(long long x) {
    if(x >= n) {
        dp[x] = bruh[x];
        br[x] = 0;
        return;
    }
    build(x*2+1);
    build(x*2+2);
    dp[x] = (p2[br[x*2+1]]*(dp[x*2+1]+dp[x*2+2]))%MOD;
    br[x] = br[x*2+1]*2+1;
}

void init(int N, int M, vector<int> p, vector<int> a) {
    p2[0] = 1;
    for(int i = 1; i < 300001; i++) {
        p2[i] = (p2[i-1]*2)%MOD;
    }
    n = N;
    m = M;
    for(int i = n; i < n+a.size(); i++) {
        bruh[i] = a[i-n];
    }
    build(0);
}

int count_ways(int l, int r) {
    upd(l-n,r-n,0,0,n);
    long long a = dp[0];
    if(f[0]%2) {
        a = (p2[br[0]]-dp[0]+MOD)%MOD;
    }
    return a;
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   58 |     for(int i = n; i < n+a.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB Output is correct
2 Correct 6 ms 11960 KB Output is correct
3 Runtime error 1406 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12000 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 6 ms 11984 KB Output is correct
4 Correct 7 ms 11984 KB Output is correct
5 Correct 7 ms 12016 KB Output is correct
6 Incorrect 6 ms 11984 KB 1st lines differ - on the 1st token, expected: '706880838', found: '530378676'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB Output is correct
2 Correct 6 ms 11960 KB Output is correct
3 Runtime error 1406 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 12784 KB Output is correct
2 Correct 612 ms 13588 KB Output is correct
3 Correct 667 ms 13536 KB Output is correct
4 Correct 543 ms 13536 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 12784 KB Output is correct
2 Correct 612 ms 13588 KB Output is correct
3 Correct 667 ms 13536 KB Output is correct
4 Correct 543 ms 13536 KB Output is correct
5 Correct 688 ms 12752 KB Output is correct
6 Correct 636 ms 13536 KB Output is correct
7 Correct 737 ms 13536 KB Output is correct
8 Correct 882 ms 13552 KB Output is correct
9 Correct 332 ms 12076 KB Output is correct
10 Correct 898 ms 12136 KB Output is correct
11 Correct 888 ms 12132 KB Output is correct
12 Correct 761 ms 12128 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12000 KB Output is correct
2 Correct 6 ms 11984 KB Output is correct
3 Correct 6 ms 11984 KB Output is correct
4 Correct 7 ms 11984 KB Output is correct
5 Correct 7 ms 12016 KB Output is correct
6 Incorrect 6 ms 11984 KB 1st lines differ - on the 1st token, expected: '706880838', found: '530378676'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB Output is correct
2 Correct 6 ms 11960 KB Output is correct
3 Runtime error 1406 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB Output is correct
2 Correct 6 ms 11960 KB Output is correct
3 Runtime error 1406 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -