Submission #683212

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
683212	2023-01-17 23:21:48	NK_	Crossing (JOI21_crossing)	C++17	100 / 100	502 ms	27536 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
using str = string;
const int MOD = 1e9 + 7;
struct Seg {
  const ll ID = 0; 
  vector<ll> pw, P;
  vector<ll> seg, lz, LX, RX; int N, B; ll cmb(int a, int b) {
    int len = RX[a] - LX[a] + 1;
    return (seg[a] + (pw[__lg(len)] * seg[b])) % MOD;
  };
  void init(int n, int b) {
    N = 1; while(N < n) N *= 2;
    B = b;
    seg.assign(2*N, ID), lz.assign(2*N, ID);
    LX.assign(2*N, -1), RX.assign(2*N, -1);
    pw = {B}; for(int i = 1; i <= __lg(N); i++) pw.push_back((pw.back() * 1LL * pw.back()) % MOD);
    P = {1}; for(int i = 1; i <= __lg(N); i++) P.push_back(((P.back() * pw[i - 1]) + P.back()) % MOD);
    build(1, 0, N-1);
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51