oj.uz

Submission #82983

# Submission time Handle Problem Language Result Execution time Memory
82983 2018-11-03T12:47:01 Z Bodo171 Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 1959 ms 263168 KB 
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=500005;
long long d[nmax],fv[nmax],val[nmax];
int n,q,p,i,l,r,t;
string s;
int num,ch;
int getnum()
{
    num=0;
    while(s[ch]>='0'&&s[ch]<='9')
        num=num*10+s[ch]-'0',ch++;
    ch++;
    return num;
}
int calc(int x,int t)
{
    int ret=0;
    int vv;
    if(t<x)
        return 0;
    for(int p=18;p>=0;p--)
    {
        vv=ret+(1<<p);
        if(vv<=n&&(t/fv[vv])*(val[vv])-vv>=x)
            ret+=(1<<p);
    }
    return ret+1;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q;getline(cin,s);
    for(i=1;i<=n;i++)
    {
        getline(cin,s);
        ch=0;d[i]=getnum();
        if(i==1) fv[i]=d[i],val[i]=d[i];
        else
        {
            if(val[i-1]<d[i])
            {
                fv[i]=(1LL*fv[i-1]*((d[i]+val[i-1]-1)/val[i-1]));
                val[i]=(d[i]+val[i-1]-(d[i]%val[i-1]));
                if(!(d[i]%val[i-1]))
                    val[i]=d[i];
            }
            else
            {
                fv[i]=fv[i-1];
                val[i]=val[i-1];
            }
            fv[i]=min(fv[i],1LL*(1000*1000*1000+1));
        }
    }
    for(i=1;i<=q;i++)
    {
        getline(cin,s);ch=0;
        t=getnum();l=getnum();r=getnum();
        cout<<calc(l,t)-calc(r+1,t)<<'\n';
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1903 ms 15432 KB Output is correct
2 Correct 1857 ms 30928 KB Output is correct
3 Correct 1892 ms 46248 KB Output is correct
4 Correct 1959 ms 61832 KB Output is correct
5 Correct 1885 ms 77284 KB Output is correct
6 Correct 1865 ms 92628 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1903 ms 15432 KB Output is correct
2 Correct 1857 ms 30928 KB Output is correct
3 Correct 1892 ms 46248 KB Output is correct
4 Correct 1959 ms 61832 KB Output is correct
5 Correct 1885 ms 77284 KB Output is correct
6 Correct 1865 ms 92628 KB Output is correct
7 Correct 5 ms 92628 KB Output is correct
8 Correct 4 ms 92628 KB Output is correct
9 Correct 5 ms 92628 KB Output is correct
10 Correct 4 ms 92628 KB Output is correct
11 Correct 5 ms 92628 KB Output is correct
12 Correct 5 ms 92628 KB Output is correct
13 Correct 1272 ms 106680 KB Output is correct
14 Correct 1305 ms 123320 KB Output is correct
15 Correct 1294 ms 138532 KB Output is correct
16 Correct 1281 ms 154408 KB Output is correct
17 Correct 1538 ms 173192 KB Output is correct
18 Correct 1516 ms 177704 KB Output is correct
19 Correct 1485 ms 177704 KB Output is correct
20 Correct 1515 ms 177704 KB Output is correct
21 Correct 1455 ms 177704 KB Output is correct
22 Correct 1469 ms 177704 KB Output is correct
23 Correct 1461 ms 195544 KB Output is correct
24 Correct 1457 ms 214148 KB Output is correct
25 Correct 1890 ms 229900 KB Output is correct
26 Correct 1955 ms 243944 KB Output is correct
27 Correct 1610 ms 259692 KB Output is correct
28 Runtime error 1516 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Halted 0 ms 0 KB -