oj.uz

Submission #911220

# Submission time Handle Problem Language Result Execution time Memory
911220 2024-01-18T16:07:25 Z lighton Street Lamps (APIO19_street_lamps) C++17
0 / 100
 5000 ms 31220 KB 
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,Q;
char S[300001];
struct Interval{
    int s,e,ts,te;
}; vector<Interval> ints;

map<int,int> stkeyf,stkeyb;
map<int,int> enkeyf,enkeyb;
void ins(int s, int e, int t){
    int now = ints.size();
    ints.push_back({s,e, t, -1});
    stkeyf.insert({s, now});
    stkeyb.insert({-s, now});
    enkeyf.insert({e, now});
    enkeyb.insert({-e, now});
}
void ers(int ind ,int t){
    ints[ind].te = t;
    int a = ints[ind].s;
    int b = ints[ind].e;
    stkeyf.erase(stkeyf.lower_bound(a));
    stkeyb.erase(stkeyb.lower_bound(-a));
    enkeyf.erase(enkeyf.lower_bound(b));
    enkeyb.erase(enkeyb.lower_bound(-b));
}

struct Event{
    int t;
    int q;
    int s,e,v;
    bool operator<(const Event &r) const{
        return t<r.t;
    }
}; vector<Event> events;

int isq[300001];
int ans[300001];

void dnc(int s, int e){
    int m = s+e>>1;
    forf(i,s,e){
        forf(j,i+1,e){
            if(events[i].q == 0 && events[j].q == 1){
                if(events[i].s <= events[j].s && events[j].e <= events[i].e){
                    ans[events[j].t] += events[i].v;
                }
            }
        }
    }
    return;
    dnc(s,m);
    dnc(m+1,e);
}

int main(){
    scanf("%d %d" , &N,&Q);
    scanf("%s" ,S); S[N] = '0';

    {
        int l = 1;
        forf(i, 1, N) {
            if (S[i - 1] == '0' && S[i] == '1') l = i+1;
            if (S[i - 1] == '1' && S[i] == '0') {
                ins(l,i,1);
            }
        }
    }

    forf(i,2,Q+1){ // t = i
        char s[10]; int a,b;
        scanf("%s" , s);
        if(s[0] == 'q'){
            isq[i] = 1;
            scanf("%d %d" , &a,&b); b--;
            events.push_back({i,1,a,b});
            if(enkeyf.lower_bound(b) != enkeyf.end()) {
                int ind = enkeyf.lower_bound(b)->second;
                if (ints[ind].s <= a && b <= ints[ind].e) ans[i] += (i - ints[ind].ts);
            }
        }
        else{
            scanf("%d" , &a);
            if(S[a-1] == '0'){
                S[a-1] = '1';
                int l = a, r = a;
                if(stkeyb.lower_bound(-a) != stkeyb.end()) {
                    int indl = stkeyb.lower_bound(-a)->second;
                    if (ints[indl].e + 1 == a) {
                        ers(indl, i - 1);
                        l = ints[indl].s;
                    }
                }

                if(enkeyf.lower_bound(a) != enkeyf.end()) {
                    int indr = enkeyf.lower_bound(a)->second;
                    if (ints[indr].s - 1 == a) {
                        ers(indr, i - 1);
                        r = ints[indr].e;
                    }
                }

                ins(l,r,i);
            }
            else{
                S[a-1] = '0';
                int ind = enkeyf.lower_bound(a)->second;
                ers(ind,i-1);
                if(ints[ind].s < a) ins(ints[ind].s , a-1 , i);
                if(ints[ind].e > a) ins(a+1 , ints[ind].e , i);
            }
        }
    }

    for(auto i : ints){
        if(i.te != -1) events.push_back({i.te,0,i.s,i.e,i.te-i.ts+1});
    }
    sort(all(events));
    dnc(0,events.size()-1);

    forf(i,1,Q+1){
        if(isq[i]) printf("%d\n" , ans[i]);
    }
}

Compilation message

street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int m = s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d %d" , &N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%s" ,S); S[N] = '0';
      |     ~~~~~^~~~~~~~~
street_lamps.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%s" , s);
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             scanf("%d %d" , &a,&b); b--;
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d" , &a);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5010 ms 20204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Incorrect 3 ms 2508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Execution timed out 5046 ms 31220 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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