結果

問題 No.752 mod数列
ユーザー たこし
提出日時 2018-11-09 22:38:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 409 ms / 2,000 ms
コード長 3,310 bytes
コンパイル時間 2,506 ms
コンパイル使用メモリ 205,684 KB
最終ジャッジ日時 2025-01-06 16:10:22
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void Node::debugPrint()’:
main.cpp:48:25: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘long long int’ [-Wformat=]
   48 |     fprintf(stderr, "l:%d, r:%d, p:%d, lValue:%d rValue:%d sumValue:%d\n", l, r, p, lValue, rValue, sumValue);
      |                        ~^                                                  ~
      |                         |                                                  |
      |                         int                                                long long int
      |                        %lld
main.cpp:48:31: warning: format ‘%d’ expects argument of type ‘int’, but argument 4 has type ‘long long int’ [-Wformat=]
   48 |     fprintf(stderr, "l:%d, r:%d, p:%d, lValue:%d rValue:%d sumValue:%d\n", l, r, p, lValue, rValue, sumValue);
      |                              ~^                                               ~
      |                               |                                               |
      |                               int                                             long long int
      |                              %lld
main.cpp:48:37: warning: format ‘%d’ expects argument of type ‘int’, but argument 5 has type ‘long long int’ [-Wformat=]
   48 |     fprintf(stderr, "l:%d, r:%d, p:%d, lValue:%d rValue:%d sumValue:%d\n", l, r, p, lValue, rValue, sumValue);
      |                                    ~^                                            ~
      |                                     |                                            |
      |                                     int                                          long long int
      |                                    %lld
main.cpp:48:48: warning: format ‘%d’ expects argument of type ‘int’, but argument 6 has type ‘long long int’ [-Wformat=]
   48 |     fprintf(stderr, "l:%d, r:%d, p:%d, lValue:%d rValue:%d sumValue:%d\n", l, r, p, lValu

ソースコード

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