第3回 ドワンゴからの挑戦状 本選(オープンコンテスト)

Submission #1227819

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)


int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
map<int, int> enumpr(int n) {
    map<int, int> V;
    for (int i = 2; i*i <= n; i++) while (n%i == 0) V[i]++, n /= i;
    if (n>1) V[n]++;
    return V;
}
//-----------------------------------------------------------------------------------
int N, Q, X[101010], L[101010], R[101010];
int ans[101010];
int S = 765;
//-----------------------------------------------------------------------------------
map<int, int> cnt;
void remove(int i) {
    if (i < 0) return;
    auto e = enumpr(X[i]);
    for (auto p : e) cnt[p.first] -= p.second;
}
void add(int i) {
    if (i < 0) return;
    auto e = enumpr(X[i]);
    for (auto p : e) cnt[p.first] += p.second;
}
int get() {
    int ret = 1;
    for (auto p : cnt) ret = mul(ret, p.second + 1);
    return ret;
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> N >> Q;
    rep(i, 0, N) scanf("%d", &X[i]);
    rep(i, 0, Q) scanf("%d%d", &L[i], &R[i]);
    rep(i, 0, Q) L[i]--, R[i]--;

    vector<int> ord;
    rep(i, 0, Q) ord.push_back(i);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        if (L[a] / S != L[b] / S) return L[a] / S < L[b] / S;
        else return R[a] < R[b];
    });

    int i = -1, j = -1;
    rep(_i, 0, Q) {
        int o = ord[_i];

        while (i < L[o]) remove(i++);
        while (i > L[o]) add(--i);
        while (j < R[o]) add(++j);
        while (j > R[o]) remove(j--);

        ans[o] = get();
    }

    rep(i, 0, Q) printf("%d\n", ans[i]);
}

Submission

Task問題 B - ニワンゴくんの約数
User nameユーザ名 はまやんはまやん
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 0
Source lengthソースコード長 1932 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i, 0, N) scanf("%d", &X[i]);
^
./Main.cpp:42:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i, 0, Q) scanf("%d%d", &L[i], &R[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt
All 0 / 1100 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,s1.txt,s2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt TLE
02.txt TLE
03.txt TLE
04.txt TLE
05.txt TLE
06.txt TLE
07.txt TLE
08.txt TLE
09.txt TLE
10.txt TLE
11.txt TLE
12.txt TLE
13.txt TLE
14.txt TLE
15.txt TLE
16.txt TLE
17.txt TLE
18.txt TLE
19.txt TLE
20.txt TLE
21.txt TLE
22.txt TLE
s1.txt AC 1 ms 256 KB
s2.txt AC 1 ms 256 KB