oj.uz

답안 #1045188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045188 2024-08-05T18:20:58 Z mychecksedad 가로등 (APIO19_street_lamps) C++17
20 / 100
 5000 ms 101068 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 2e6+100, M = 3e5+10, K = 52, MX = 30;


struct Node{
  int X, sum = 0, sum2 = 0;
  int Y, val;
  Node *L, *R;
  Node(){}
  Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
};
typedef Node* Nodep; 
 
void upd_sz(Nodep v){
  if(v){
    v->sum = v->val * v->X;
    v->sum2 = v->val;
    if(v->L) v->sum += v->L->sum;
    if(v->R) v->sum += v->R->sum;

    if(v->L) v->sum2 += v->L->sum2;
    if(v->R) v->sum2 += v->R->sum2;
  }
}

 
pair<Nodep, Nodep> split(Nodep v, int key){
  if(!v){
    return {v, v};
  }
  else if(v->X <= key){
    auto p = split(v->R, key);
    v->R = p.first;
    upd_sz(v);
    return {v, p.second};
  }else{
    auto p = split(v->L, key);
    v->L = p.second;
    upd_sz(v);
    return {p.first, v};
  }
}
 
Nodep merge(Nodep l, Nodep r){
  if(!l || !r){
    return l ? l : r;
  }else if(l->Y > r->Y){
    auto p = merge(l->R, r);
    l->R = p;
    upd_sz(l);
    return l;
  }else{
    auto p = merge(l, r->L);
    r->L = p;
    upd_sz(r);
    return r;
  }
}
Nodep insert(Nodep v, Nodep it){
  auto a = split(v, it->X);
  return merge(merge(a.first, it), a.second);
}

void dfs(Nodep t){
  if(t->L) dfs(t->L);
  if(t->R) dfs(t->R);
  free(t);
}
 

int n, q, ans[M];
string s;
Nodep T[N];

void build(int l, int r, int k){
  if(l == r){
    T[k] = new Node(0, 0);
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = new Node(0, 0);
}

void upd(int l, int r, int p, int k, int t1, int t2){
  if(!(l == 1 && r == n + 1)){
    Nodep A = new Node(t1, 1);
    Nodep B = new Node(t2, -1);
    T[k] = insert(T[k], A);
    T[k] = insert(T[k], B);
  }
  if(l == r){
    return;
  }
  int m = l+r>>1;
  if(p <= m) upd(l, m, p, k<<1, t1, t2);
  else upd(m+1, r, p, k<<1|1, t1, t2);
}

int get(int l, int r, int p, int k, ll tm){
  if(l == r){
    int val = 0;
    auto halves = split(T[k], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
    T[k] = merge(halves.ff, halves.ss);
    return val;
  }
  int m = l+r>>1;
  if(p <= m){
    int val = 0;
    auto halves = split(T[k<<1|1], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
    T[k<<1|1] = merge(halves.ff, halves.ss);
    return get(l, m, p, k<<1, tm) + val;
  }
  return get(m+1, r, p, k<<1|1, tm);
}

void F(int l, int r, int p, int k){
  if(l == r){
    dfs(T[k]);
    return;
  }
  int m = l+r>>1;
  if(p <= m) F(l, m, p, k<<1);
  else F(m+1, r, p, k<<1|1);
  if(p == r) dfs(T[k]);
}

vector<array<int, 3>> Q[M];
void solve(){
  // cout << sizeof(Node) << '\n';
  cin >> n >> q >> s;

  vector<array<int, 4>> R;
  int last = 1;
  s += '0';
  set<array<int, 3>> S;
  for(int i = 0; i <= n; ++i){
    if(s[i] == '0'){
      S.insert({last, i + 1, 0});
      last = i + 2;
    }
  }

  int qq = 0;

  for(int i = 0; i < q; ++i){
    string x; int a, b; cin >> x;
    if(x == "toggle"){
      cin >> a;
      --a;
      if(s[a] == '0'){
        s[a] = '1';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        auto it2 = prev(it);
        auto x = *it, y = *it2;
        S.erase(it2);
        S.erase(S.find(x));
        S.insert({y[0], x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
        R.pb({y[0], y[1], y[2], i + 1});
      }else{
        s[a] = '0';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto x = *it;
        S.erase(it);
        S.insert({x[0], a, i + 1}); // check
        S.insert({a + 1, x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
      }
    }else{
      cin >> a >> b;
      Q[a].pb({b, i + 1, qq});
      qq++;
    }
  }

  for(auto p: S){
    R.pb({p[0], p[1], p[2], q});
  }
  S.clear();

  sort(all(R));
  build(1, n + 1, 1);
  int p = 0;
  for(int l = 1; l <= n + 1; ++l){
    while(p < R.size() && R[p][0] == l){
      int r = R[p][1], t1 = R[p][2], t2 = R[p][3];
      upd(1, n+1, r, 1, t1, t2);
      ++p;
    }
    for(auto query: Q[l]){
      int r = query[0], tm = query[1], idx = query[2];
      ans[idx] = get(1, n + 1, r, 1, tm);
    }
    F(1, n+1, l, 1);
  }



  for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

street_lamps.cpp: In constructor 'Node::Node(int, int)':
street_lamps.cpp:18:13: warning: 'Node::R' will be initialized after [-Wreorder]
   18 |   Node *L, *R;
      |             ^
street_lamps.cpp:17:10: warning:   'int Node::val' [-Wreorder]
   17 |   int Y, val;
      |          ^~~
street_lamps.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp:17:10: warning: 'Node::val' will be initialized after [-Wreorder]
   17 |   int Y, val;
      |          ^~~
street_lamps.cpp:16:10: warning:   'int Node::sum' [-Wreorder]
   16 |   int X, sum = 0, sum2 = 0;
      |          ^~~
street_lamps.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:90:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:106:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:119:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:135:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:204:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:224:15: warning: unused variable 'aa' [-Wunused-variable]
  224 |   int tt = 1, aa;
      |               ^~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1534 ms 40944 KB Output is correct
2 Correct 1920 ms 40032 KB Output is correct
3 Correct 2787 ms 39996 KB Output is correct
4 Correct 4888 ms 79816 KB Output is correct
5 Correct 3096 ms 72884 KB Output is correct
6 Execution timed out 5062 ms 88932 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11100 KB Output is correct
2 Correct 7 ms 11100 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Execution timed out 5101 ms 101068 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 5 ms 10844 KB Output is correct
3 Correct 7 ms 11120 KB Output is correct
4 Correct 8 ms 11100 KB Output is correct
5 Correct 1374 ms 62220 KB Output is correct
6 Correct 3249 ms 72056 KB Output is correct
7 Execution timed out 5019 ms 83428 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 1534 ms 40944 KB Output is correct
9 Correct 1920 ms 40032 KB Output is correct
10 Correct 2787 ms 39996 KB Output is correct
11 Correct 4888 ms 79816 KB Output is correct
12 Correct 3096 ms 72884 KB Output is correct
13 Execution timed out 5062 ms 88932 KB Time limit exceeded
14 Halted 0 ms 0 KB -