oj.uz

답안 #943326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943326 2024-03-11T10:48:24 Z Alkarat Sum Zero (RMI20_sumzero) C++14
100 / 100
 455 ms 14388 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define ldb long double
#define db double
#define fin(x) freopen(x,"r",stdin)
#define fout(x) freopen(x,"w",stdout)
#define fo(i,l,r) for(int i=(l);i<=(r);i++)
#define foi(i,l,r) for(int i=(l);i>=(r);i--)
#define el cout<<'\n';
#define cel cerr<<'\n';
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define gb(x,i) (((x)>>(i))&1)
#define mask(i) (1LL<<(i))
#define TIME (1.0 * clock()/CLOCKS_PER_SEC)
using namespace std;
const int N=4e5+1;
const int bl=350;
const ll base=1e9+7;
const ll inf=1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l,ll r)
{
    return l+(1ll*rng()*rng()%(r-l+1)+(r-l+1))%(r-l+1);
}
template<class X,class Y>bool maximize(X &a,Y b)
{
    if(a<b) return a=b,true;
    return false;
}
template<class X,class Y>bool minimize(X &a, Y b)
{
    if(a>b) return a=b,true;
    return false;
}
void add(auto &a,auto b)
{
    a+=b;
    if(a>=base) a-=base;
    if(a<0) a+=base;
}
int n,x,nxt[N][3],q;
int pw[3],pos[N],a[N],l,r,ans;
vector<ll>cc;
void solve()
{
    ans=0;
    cin>>l>>r,l--;
    foi(i,2,0) while(nxt[l][i]<=r) ans+=pw[i],l=nxt[l][i];
    cout<<ans,el
}
int main()
{
    #define task "o"
    if(fopen(task".inp","r"))
    {
        fin(task".inp");
        fout(task".out");
    }
    srand(time(NULL));
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    ll now=0;
    fo(i,1,n)
    {
        cin>>a[i];
        now+=a[i],cc.pb(now);
    }
    cc.pb(0);
    sort(all(cc)),cc.erase(unique(all(cc)),cc.end());
    now=0;
    fo(i,0,n)
    {
        now+=a[i];
        a[i]=lower_bound(all(cc),now)-cc.begin();
    }
    nxt[n+1][0]=n+1;
    foi(i,n,0)
    {
        if(pos[a[i]]) nxt[i][0]=min(nxt[i+1][0],pos[a[i]]);
        else nxt[i][0]=nxt[i+1][0];
        pos[a[i]]=i;
    }
    pw[0]=1;
    fo(i,1,2) pw[i]=pw[i-1]*47;
    fo(x,1,2) fo(i,0,n)
    {
        int pos=nxt[i][x-1];
        fo(c,1,46) if(pos<=n) pos=nxt[pos][x-1];
        nxt[i][x]=pos;
    }
    cin>>q;
    while(q--) solve();
    cerr<<"Time elapsed: "<<TIME<<" s.\n";
}

Compilation message

sumzero.cpp:41:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   41 | void add(auto &a,auto b)
      |          ^~~~
sumzero.cpp:41:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   41 | void add(auto &a,auto b)
      |                  ^~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:9:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define fin(x) freopen(x,"r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~
sumzero.cpp:62:9: note: in expansion of macro 'fin'
   62 |         fin(task".inp");
      |         ^~~
sumzero.cpp:10:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define fout(x) freopen(x,"w",stdout)
      |                 ~~~~~~~^~~~~~~~~~~~~~
sumzero.cpp:63:9: note: in expansion of macro 'fout'
   63 |         fout(task".out");
      |         ^~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 84 ms 7976 KB Output is correct
8 Correct 66 ms 8064 KB Output is correct
9 Correct 92 ms 8144 KB Output is correct
10 Correct 82 ms 7964 KB Output is correct
11 Correct 67 ms 7992 KB Output is correct
12 Correct 91 ms 8136 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 84 ms 7976 KB Output is correct
8 Correct 66 ms 8064 KB Output is correct
9 Correct 92 ms 8144 KB Output is correct
10 Correct 82 ms 7964 KB Output is correct
11 Correct 67 ms 7992 KB Output is correct
12 Correct 91 ms 8136 KB Output is correct
13 Correct 418 ms 14272 KB Output is correct
14 Correct 348 ms 12360 KB Output is correct
15 Correct 449 ms 14388 KB Output is correct
16 Correct 432 ms 12656 KB Output is correct
17 Correct 306 ms 13716 KB Output is correct
18 Correct 455 ms 14196 KB Output is correct