結果

問題 No.752 mod数列
ユーザー たこしたこし
提出日時 2018-11-09 22:38:12
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 366 ms / 2,000 ms
コード長 3,310 bytes
コンパイル時間 2,644 ms
コンパイル使用メモリ 208,688 KB
実行使用メモリ 13,580 KB
最終ジャッジ日時 2023-08-13 11:55:45
合計ジャッジ時間 10,047 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
4,384 KB
testcase_01 AC 5 ms
4,384 KB
testcase_02 AC 4 ms
4,380 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 3 ms
4,384 KB
testcase_05 AC 5 ms
4,384 KB
testcase_06 AC 4 ms
4,384 KB
testcase_07 AC 5 ms
4,380 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 5 ms
4,380 KB
testcase_10 AC 88 ms
13,192 KB
testcase_11 AC 43 ms
7,428 KB
testcase_12 AC 75 ms
11,840 KB
testcase_13 AC 57 ms
7,788 KB
testcase_14 AC 91 ms
13,032 KB
testcase_15 AC 190 ms
4,380 KB
testcase_16 AC 357 ms
13,124 KB
testcase_17 AC 366 ms
13,580 KB
testcase_18 AC 200 ms
4,384 KB
testcase_19 AC 224 ms
4,516 KB
testcase_20 AC 220 ms
4,392 KB
testcase_21 AC 223 ms
4,400 KB
testcase_22 AC 216 ms
4,380 KB
testcase_23 AC 229 ms
4,600 KB
testcase_24 AC 221 ms
4,380 KB
testcase_25 AC 169 ms
12,176 KB
testcase_26 AC 287 ms
13,032 KB
testcase_27 AC 215 ms
11,980 KB
testcase_28 AC 270 ms
13,544 KB
testcase_29 AC 274 ms
12,324 KB
testcase_30 AC 286 ms
12,172 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 70 ms
12,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

int P;
int Q;

struct Node {
  int l, r;
  int p;
  int lValue, rValue;
  int sumValue;

  Node() {
    l = 1145141919;
    r = 0;
    p = lValue = rValue = sumValue = 0;
  }

  bool operator < (const Node& n) const {
    return l < n.l;
  }

  void debugPrint() 
  {
    fprintf(stderr, "l:%d, r:%d, p:%d, lValue:%d rValue:%d sumValue:%d\n", l, r, p, lValue, rValue, sumValue);
  }
};

vector<Node> vec;

class SegmentTree{
public:
  SegmentTree(int size) {
    init(size);
  }

  void init(int size) {
    vec.clear();
    k = 1;
    while(k < size) {
      k *= 2;
    }
    REP(i,2*k) {
      vec.push_back(Node());
    }
    lastPos = k-1;
  }

  void set(int i, Node node) {
    i += k-1;
    vec[i] = node;
    while(i > 0) {
      i = (i-1)/2;
      Node& n = vec[i];
      Node& l = vec[i*2+1];
      Node& r = vec[i*2+2];
      n.l = min(n.l, min(l.l, r.l));
      n.r = max(n.r, max(l.r, r.r));
      n.sumValue = l.sumValue + r.sumValue;
    }
  }

  int find(int l, int r, int pos = 0) {
    Node& n = vec[pos];
    int x = n.l;
    int y = n.r;
    // cerr << pos << ": " << x << " " << y << " " << l << " " << r << endl;
    // cerr << "bool: " << (r < x || y < l) << endl;
    
    if(r < x || y < l) {
      // cerr << "0!!!" << endl;
      return 0;
    }
    
    if(lastPos <= pos) {
      int ll = max(l,x);
      int rr = min(r,y);
      int llValue = n.lValue - n.p*(ll-n.l);
      int rrValue = n.lValue - n.p*(rr-n.l);
      return (llValue+rrValue)*(rr-ll+1)/2;
    } else {
      if(l <= x && y <= r) {
        return vec[pos].sumValue;
      } else {
        return find(l,r,2*pos+1) + find(l,r,2*pos+2);
      }
    }
  }

  vector<Node> vec;
  int k;
  int lastPos;
};

signed main()
{
  cin >> P >> Q;
  int r = P;
  int l = 1;
  while(l<=r) {
    Node lNode; lNode.l = lNode.r = lNode.p  = l;
    lNode.rValue = lNode.lValue = lNode.sumValue = P%l;
    vec.push_back(lNode);
    if(!(l<r)) {
      break;
    }
    Node node;
    node.r = r;
    node.rValue = P%l;
    node.l = r - (r - node.rValue-1)/(l+1);
    node.p = l;
    node.lValue = node.rValue + node.p * (node.r-node.l);
    node.sumValue = (node.lValue + node.rValue)*(node.r-node.l+1)/2;
    vec.push_back(node);
    l++;
    r = node.l-1;
  }

  

  sort(begin(vec), end(vec));
  // cerr << vec.size() << endl;
  for(auto v : vec) {
    v.debugPrint();
  }

  SegmentTree segTree(vec.size());
  REP(i,vec.size()) {
    segTree.set(i,vec[i]);
  }

  // cerr << segTree.find(7,13) << endl;

  REP(q,Q) {
    int l, r;
    cin >> l >> r;
    if(P < l) {
      cout << P*(r-l+1) << endl;
    } else if(P < r) {
      cout << P*(r-P) + segTree.find(l,P) << endl;
    } else {
      cout << segTree.find(l,r) << endl;
    }
  }

  return 0;
}
0