oj.uz

Submission #405143

# Submission time Handle Problem Language Result Execution time Memory
405143 2021-05-15T18:35:14 Z A_D Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1815 ms 118108 KB 
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=3e5+100;
int seg[4*N];
map<ii,int> ans;
map<int,int> l;
map<int,int> r;
set<int> st[N];
string qu[N];
int a[N];
int b[N];
void build(int p,int s,int e)
{
    if(s==e){
        seg[p]=*st[s].begin();
        return;
    }
    int mid=(s+e)/2;
    build(p*2,s,mid);
    build(p*2+1,mid+1,e);
    seg[p]=min(seg[p*2],seg[p*2+1]);
}
void update(int p,int s,int e,int l1,int r1,int l2,int r2,int v)
{
    if(s>r1||e<l1||seg[p]>r2){
        return;
    }
    if(s==e){
        while(1){
            int u=*st[s].lower_bound(l2);
            if(u>r2)break;
            ans[{s,u}]=v;
            st[s].erase(u);
        }
        seg[p]=*st[s].begin();
        return;
    }
    int mid=(s+e)/2;
    update(p*2,s,mid,l1,r1,l2,r2,v);
    update(p*2+1,mid+1,e,l1,r1,l2,r2,v);
    seg[p]=min(seg[p*2],seg[p*2+1]);
}
void solve()
{
    int n,q;
    cin>>n>>q;
    n++;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++)st[i].insert(1e8);
    for(int i=1;i<=q;i++){
        cin>>qu[i];
        if(qu[i]=="query"){
            scanf("%lld",&a[i]);
            scanf("%lld",&b[i]);
            st[a[i]].insert(b[i]);
        }
        else{
            scanf("%lld",&a[i]);
        }
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        l[i]=i;
        r[i]=i;
    }
    for(int i=1;i<n;i++){
        if(s[i-1]=='1'){
            update(1,1,n,l[i],r[i],l[i+1],r[i+1],0);
            r[l[i]]=r[i+1];
            l[r[i+1]]=l[i];
        }
    }
    //cout<<5<<endl;
    for(int i=1;i<=q;i++){
        if(qu[i]=="query"){
            if(ans.count({a[i],b[i]})==0){
                printf("0\n");
            }
            else{
      //          cout<<ans[{a[i],b[i]}]<<" ";
                int u=i-ans[{a[i],b[i]}];
                printf("%lld\n",u);
            }
        }
        else{
            int j=a[i];
            update(1,1,n,l[j],r[j],l[j+1],r[j+1],i);
            r[l[j]]=r[j+1];
            l[r[j+1]]=l[j];
        }
    }
}

main()
{
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Compilation message

street_lamps.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main()
      | ^~~~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             scanf("%lld",&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("%lld",&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%lld",&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 31636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24004 KB Output is correct
2 Correct 16 ms 23960 KB Output is correct
3 Correct 17 ms 24068 KB Output is correct
4 Correct 20 ms 24112 KB Output is correct
5 Correct 1341 ms 93416 KB Output is correct
6 Correct 1323 ms 100020 KB Output is correct
7 Correct 1264 ms 107108 KB Output is correct
8 Correct 1815 ms 117888 KB Output is correct
9 Correct 175 ms 31688 KB Output is correct
10 Correct 196 ms 32224 KB Output is correct
11 Correct 195 ms 32628 KB Output is correct
12 Correct 571 ms 109268 KB Output is correct
13 Correct 1810 ms 118108 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Incorrect 16 ms 24060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23780 KB Output isn't correct
2 Halted 0 ms 0 KB -