oj.uz

Submission #166229

# Submission time Handle Problem Language Result Execution time Memory
166229 2019-12-01T11:21:12 Z georgerapeanu Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 833 ms 36484 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 5e5;
const int QMAX = 5e5;

int n,q;
int d[NMAX + 5];

struct query_t{
    int t,l,r;
    int ans;
    int id;

    bool operator < (const query_t &other)const{
        if(t < other.t){
            return t < other.t;
        }
        return id < other.id;
    }

}query[NMAX + 5];

int aib[NMAX + 5];

void aib_update(int pos,int val){
    for(;pos <= n;pos += (-pos) & pos){
        aib[pos] += val;
    }
}

int aib_query(int pos){
    int ans = 0;

    for(;pos;pos -= (-pos) & pos){
        ans += aib[pos];
    }

    return ans;
}

int main(){

    scanf("%d %d",&n,&q);

    for(int i = 1;i <= n;i++){
        scanf("%d",&d[i]);
    }

    for(int i = 2;i <= n;i++){
        d[i] = ((d[i] / d[i - 1]) + (d[i] % d[i - 1] != 0)) * d[i - 1];
    }

    for(int i = 1;i <= q;i++){
        scanf("%d %d %d",&query[i].t,&query[i].l,&query[i].r);
        query[i].id = i;
        query[i].ans += (query[i].l <= query[i].t && query[i].t <= query[i].r);
    }

    vector<int> pos = {1};
    for(int i = 2;i <= n + 1;i++){
        if(i == n + 1 || d[i] != d[i - 1]){
            int per = d[i - 1];

            for(auto it:pos){
                aib_update(it,1);
            }

            for(int i = 1;i <= q;i++){
                int l = query[i].l - (query[i].t / per) * per;
                int r = query[i].r - (query[i].t / per) * per;
                r = min(r,-1);
                l = max(l,-n);
                if(l <= r){
                    l = -l;
                    r = -r;
                    query[i].ans += aib_query(l) - aib_query(r - 1);
                    
                }
            }

            for(auto it:pos){
                aib_update(it,-1);
            }

            pos.clear();
        }
        pos.push_back(i);
    }

    for(int i = 1;i <= q;i++){
        printf("%d\n",query[i].ans);
    }

    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&d[i]);
         ~~~~~^~~~~~~~~~~~
worst_reporter3.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&query[i].t,&query[i].l,&query[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 34916 KB Output is correct
2 Correct 417 ms 34780 KB Output is correct
3 Correct 421 ms 34668 KB Output is correct
4 Correct 413 ms 34660 KB Output is correct
5 Correct 421 ms 34832 KB Output is correct
6 Correct 409 ms 34532 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 34916 KB Output is correct
2 Correct 417 ms 34780 KB Output is correct
3 Correct 421 ms 34668 KB Output is correct
4 Correct 413 ms 34660 KB Output is correct
5 Correct 421 ms 34832 KB Output is correct
6 Correct 409 ms 34532 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 408 ms 33208 KB Output is correct
14 Correct 415 ms 33760 KB Output is correct
15 Correct 395 ms 32612 KB Output is correct
16 Correct 410 ms 32912 KB Output is correct
17 Correct 705 ms 36076 KB Output is correct
18 Correct 660 ms 35916 KB Output is correct
19 Correct 712 ms 36020 KB Output is correct
20 Correct 691 ms 35900 KB Output is correct
21 Correct 679 ms 35940 KB Output is correct
22 Correct 685 ms 36168 KB Output is correct
23 Correct 672 ms 35836 KB Output is correct
24 Correct 670 ms 36168 KB Output is correct
25 Correct 444 ms 33664 KB Output is correct
26 Correct 501 ms 33884 KB Output is correct
27 Correct 778 ms 36004 KB Output is correct
28 Correct 828 ms 36484 KB Output is correct
29 Correct 833 ms 35768 KB Output is correct
30 Correct 802 ms 35560 KB Output is correct
31 Correct 812 ms 36444 KB Output is correct
32 Correct 398 ms 32152 KB Output is correct
33 Correct 3 ms 376 KB Output is correct