Submission #908879

#	Time	Username	Problem	Language	Result	Execution time	Memory
908879		vjudge1	Secret (JOI14_secret)	C++17	30 / 100	446 ms	4464 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;

// int Secret(int X, int Y)
// ll COUNT = 0;
// int Secret (int X, int Y) {
//   COUNT++;
//   // if (X > 1E9-Y) return 1E9;
//   return (X+Y)%10000000;
// }

// struct Segment {
//   int l, r, id;

//   Segment (int l, int r, int id): l(l), r(r), id(id) {}
// };

// int dp[1005][1005];
// bool vis[1005][1005];
// vector <Segment> nivs[12];

struct SegTree {
  vector <int> tree;
  int n;

  void build (vector <int> ve, int l, int r, int id, int niv) {
    // nivs[niv].push_back(Segment(l, r, id));
    if (l==r) {
      tree[id] = ve[l];
      // dp[l][r] = tree[id];
      // vis[l][r] = true;
      return;
    }
    int mid = (l+r)>>1;
    build(ve, l, mid, 2*id+1, niv+1);
    build(ve, mid+1, r, 2*id+2, niv+1);
    tree[id] = Secret(tree[2*id+1], tree[2*id+2]);
    // dp[l][r] = tree[id];
    // vis[l][r] = true;
    return;
  }

  void init (int n, vector <int>& ve) {
    n=(n);
    tree.resize(4*n);
    // n = (1<<(__lg(n-1)));
    // build(ve, 0, n-1, 0, 0);
    build(ve, 0, n-1, 0, 0);
    return;
  }

  int query (int ql, int qr, int l, int r, int id) {
    if (qr < l || r < ql) return -1;
    if (ql <= l && r <= qr) return tree[id];
    int mid = (l+r)>>1;
    int ansl = query(ql, qr, l, mid, 2*id+1);
    int ansr = query(ql, qr, mid+1, r, 2*id+2);
    if (min(ansl, ansr) == -1) return max(ansl, ansr);
    return Secret(ansl, ansr);
  }

  // void solve (int niv) {
  //   if (niv == 0) return;
  //   vector <Segment> vn = nivs[niv];
  //   // for (Segment s : vn) {
  //   //   cout<<s.l<<' ' << s.r<<' '<<s.id<<'\n';
  //   // }
  //   // cout<<endl;
    
  //   // for (int i = 1; i < vn.size(); i++) {
  //   //   Segment ant = vn[i-1];
  //   //   Segment act = vn[i];
  //   //   // if (!(ant.r+1==act.l)) {
  //   //   //   cerr<<niv<<'\n'<<i<<'\n';
  //   //   //   cerr<<nivs[niv].size()<<'\n';
  //   //   // }
  //   //   assert(ant.r+1==act.l);
  //   // }
  //   // solve(niv-1);
  //   // return;
  //   for (int i = 1; i < vn.size(); i++) {
  //     Segment ant = vn[i-1];
  //     Segment act = vn[i];
  //     // assert(ant.r+1==act.l);
  //     for (int j = act.l; j <= min(act.r,n-1); j++) {
  //       assert(vis[act.l][j]);
  //       dp[ant.l][j] = Secret(dp[ant.l][ant.r], dp[act.l][j]);
  //       vis[ant.l][j] = true;
  //     }
  //     if(act.r>=n-1)break;
  //   }
  //   for (int i = 1; i < vn.size(); i++) {
  //     Segment ant = vn[i-1];
  //     Segment act = vn[i];
  //     for (int j = ant.l; j <= min(ant.r,n-1); j++) {
  //       assert(vis[j][ant.r]);
  //       dp[j][act.r] = Secret(dp[j][ant.r], dp[act.l][act.r]);
  //       vis[j][act.r] = true;
  //     }
  //     if(ant.r>=n-1)break;
  //   }
  //   // if (vis[ql][qr]) return dp[ql][qr];
  //   // vis[ql][qr] = true;
  //   // ll& ans = dp[ql][qr];
  //   solve(niv-1);
  //   return;
  // }
};

int nn;
SegTree st;

void Init (int n, int a[]) {
  nn=n;
  vector <int> ve(n);
  for (int i = 0; i < n; i++) {
    ve[i] = a[i];
  }
  st.init(n, ve);
  // for (ll i = 0; i < n; i++) {
  //   for (ll j = i; j < n; j++) {
  //     cerr<<i<<','<<j<<": "<<dp[i][j]<<'\n';
  //   }
  // }
  // st.solve(11);
  return;
}

int Query (int l, int r) {
  // cout << "counter: " << COUNT << '\n';
  return st.query(l, r, 0, nn-1, 0);
}

// int main () {
//   int n;
//   cin >> n;
//   int a[n];
//   for (int i = 0; i < n; i++) cin >> a[i];
//   Init(n, a);
//   ll Q;
//   cin >> Q;
//   while(Q--){
//     ll l,r;
//     cin>>l>>r;
//     cout<<Query(l,r)<<'\n';
//   }
//   return 0;
// }

• Subtask 1: 30 / 100