oj.uz

Submission #123656

# Submission time Handle Problem Language Result Execution time Memory
123656 2019-07-01T22:40:57 Z duality Street Lamps (APIO19_street_lamps) C++11
100 / 100
 2355 ms 201528 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

struct event { int x,t,l,r,k; };
bool comp(event a,event b) {
    if (a.x == b.x) return abs(a.k) > abs(b.k);
    else return a.x < b.x;
}
char s[300000];
set<pii> S;
vector<event> events;
LLI ans[300000];
LLI bit1[300002],bit2[300002];
struct myset {
    vpii events;
    int insert(int x) {
        events.pb(mp(x,0));
        return 0;
    }
    int query(int x,int m) {
        events.pb(mp(x,m));
        return 0;
    }
    int process(int q) {
        int i,j;
        for (i = 0; i < events.size(); i++) {
            if (events[i].second == 0) {
                for (j = events[i].first+2; j <= q; j += j & (-j)) bit1[j]++,bit2[j] += events[i].first;
            }
            else {
                LLI a = 0,b = 0;
                for (j = events[i].first+2; j > 0; j -= j & (-j)) a += bit1[j],b += bit2[j];
                ans[events[i].first] += events[i].second*(a*events[i].first-b);
            }
        }
        for (i = 0; i < events.size(); i++) {
            if (events[i].second == 0) {
                for (j = events[i].first+2; j <= q; j += j & (-j)) bit1[j] = bit2[j] = 0;
            }
        }
        return 0;
    }
};
myset tree1[1 << 20],tree2[1 << 20];
int update(int s,int e,int as,int ae,int i,int t,int k) {
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        if (k == 1) tree1[i].insert(t);
        else tree2[i].insert(t);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,t,k);
    update(mid+1,e,as,ae,2*i+2,t,k);
    return 0;
}
int query(int s,int e,int q,int i,int t) {
    if ((s > q) || (e < q)) return 0;
    else if (s == e) {
        tree1[i].query(t,1),tree2[i].query(t,-1);
        return 0;
    }

    int mid = (s+e) / 2;
    tree1[i].query(t,1),tree2[i].query(t,-1);
    query(s,mid,q,2*i+1,t),query(mid+1,e,q,2*i+2,t);
    return 0;
}
int process(int s,int e,int i,int q) {
    if (s == e) {
        tree1[i].process(q),tree2[i].process(q);
        return 0;
    }

    int mid = (s+e) / 2;
    tree1[i].process(q),tree2[i].process(q);
    process(s,mid,2*i+1,q),process(mid+1,e,2*i+2,q);
    return 0;
}
int main() {
    int i;
    int n,q,p = -1;
    int a,b,l,r;
    char o[7];
    scanf("%d %d",&n,&q);
    for (i = 0; i < n; i++) {
        scanf(" %c",&s[i]);
        if (s[i] == '0') {
            if (i-1 >= p+1) S.insert(mp(p+1,i-1));
            p = i;
        }
    }
    if (i-1 >= p+1) S.insert(mp(p+1,i-1));
    for (auto it = S.begin(); it != S.end(); it++) events.pb((event){it->first,-1,0,it->second,1});
    for (i = 0; i < q; i++) {
        scanf("%s",o);
        if (o[0] == 't') {
            scanf("%d",&p),p--;
            if (s[p] == '0') {
                auto it = S.lower_bound(mp(p,0));
                if (it == S.end()) r = p;
                else {
                    if (it->first == p+1) r = it->second,S.erase(it);
                    else r = p;
                }
                it = S.lower_bound(mp(p,0));
                if (it == S.begin()) l = p;
                else {
                    --it;
                    if (it->second == p-1) l = it->first,S.erase(it);
                    else l = p;
                }
                S.insert(mp(l,r));
                events.pb((event){l,i,p,r,1});
                events.pb((event){p+1,i,p,r,-1});
                s[p] = '1';
            }
            else {
                auto it = --S.upper_bound(mp(p,n));
                l = it->first,r = it->second,S.erase(it);
                events.pb((event){l,i,p,r,-1});
                events.pb((event){p+1,i,p,r,1});
                if (p-1 >= l) S.insert(mp(l,p-1));
                if (r >= p+1) S.insert(mp(p+1,r));
                s[p] = '0';
            }
        }
        else {
            scanf("%d %d",&a,&b);
            a--,b -= 2;
            events.pb((event){a,i,b,b,0});
        }
    }
    sort(events.begin(),events.end(),comp);

    fill(ans,ans+q,-1);
    for (i = 0; i < events.size(); i++) {
        if (events[i].k == 0) ans[events[i].t] = 0,query(0,n-1,events[i].l,0,events[i].t);
        else update(0,n-1,events[i].l,events[i].r,0,events[i].t,events[i].k);
    }
    process(0,n-1,0,q+1);
    for (i = 0; i < q; i++) {
        if (ans[i] != -1) printf("%lld\n",ans[i]);
    }

    return 0;
}

Compilation message

street_lamps.cpp: In member function 'int myset::process(int)':
street_lamps.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < events.size(); i++) {
                     ~~^~~~~~~~~~~~~~~
street_lamps.cpp:90:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < events.size(); i++) {
                     ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:192:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < events.size(); i++) {
                 ~~^~~~~~~~~~~~~~~
street_lamps.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&s[i]);
         ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",o);
         ~~~~~^~~~~~~~
street_lamps.cpp:153:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&p),p--;
             ~~~~~~~~~~~~~~^~~~
street_lamps.cpp:184:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49596 KB Output is correct
2 Correct 54 ms 49656 KB Output is correct
3 Correct 55 ms 49656 KB Output is correct
4 Correct 45 ms 49656 KB Output is correct
5 Correct 47 ms 49656 KB Output is correct
6 Correct 55 ms 49656 KB Output is correct
7 Correct 46 ms 49656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 97228 KB Output is correct
2 Correct 585 ms 103732 KB Output is correct
3 Correct 733 ms 119856 KB Output is correct
4 Correct 1516 ms 157636 KB Output is correct
5 Correct 1684 ms 165068 KB Output is correct
6 Correct 1457 ms 140840 KB Output is correct
7 Correct 1224 ms 199880 KB Output is correct
8 Correct 1260 ms 201528 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49784 KB Output is correct
2 Correct 48 ms 49840 KB Output is correct
3 Correct 48 ms 49912 KB Output is correct
4 Correct 48 ms 49984 KB Output is correct
5 Correct 1076 ms 96056 KB Output is correct
6 Correct 1754 ms 133888 KB Output is correct
7 Correct 2161 ms 165996 KB Output is correct
8 Correct 2086 ms 193464 KB Output is correct
9 Correct 356 ms 96180 KB Output is correct
10 Correct 397 ms 103632 KB Output is correct
11 Correct 390 ms 104908 KB Output is correct
12 Correct 2070 ms 192284 KB Output is correct
13 Correct 2090 ms 193168 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49912 KB Output is correct
2 Correct 49 ms 49912 KB Output is correct
3 Correct 49 ms 49896 KB Output is correct
4 Correct 57 ms 49784 KB Output is correct
5 Correct 2355 ms 201512 KB Output is correct
6 Correct 2157 ms 171652 KB Output is correct
7 Correct 1816 ms 142416 KB Output is correct
8 Correct 1307 ms 101428 KB Output is correct
9 Correct 573 ms 89272 KB Output is correct
10 Correct 531 ms 78260 KB Output is correct
11 Correct 597 ms 89168 KB Output is correct
12 Correct 524 ms 78588 KB Output is correct
13 Correct 550 ms 89020 KB Output is correct
14 Correct 507 ms 78392 KB Output is correct
15 Correct 2051 ms 189268 KB Output is correct
16 Correct 2070 ms 193232 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49596 KB Output is correct
2 Correct 54 ms 49656 KB Output is correct
3 Correct 55 ms 49656 KB Output is correct
4 Correct 45 ms 49656 KB Output is correct
5 Correct 47 ms 49656 KB Output is correct
6 Correct 55 ms 49656 KB Output is correct
7 Correct 46 ms 49656 KB Output is correct
8 Correct 567 ms 97228 KB Output is correct
9 Correct 585 ms 103732 KB Output is correct
10 Correct 733 ms 119856 KB Output is correct
11 Correct 1516 ms 157636 KB Output is correct
12 Correct 1684 ms 165068 KB Output is correct
13 Correct 1457 ms 140840 KB Output is correct
14 Correct 1224 ms 199880 KB Output is correct
15 Correct 1260 ms 201528 KB Output is correct
16 Correct 48 ms 49784 KB Output is correct
17 Correct 48 ms 49840 KB Output is correct
18 Correct 48 ms 49912 KB Output is correct
19 Correct 48 ms 49984 KB Output is correct
20 Correct 1076 ms 96056 KB Output is correct
21 Correct 1754 ms 133888 KB Output is correct
22 Correct 2161 ms 165996 KB Output is correct
23 Correct 2086 ms 193464 KB Output is correct
24 Correct 356 ms 96180 KB Output is correct
25 Correct 397 ms 103632 KB Output is correct
26 Correct 390 ms 104908 KB Output is correct
27 Correct 2070 ms 192284 KB Output is correct
28 Correct 2090 ms 193168 KB Output is correct
29 Correct 49 ms 49912 KB Output is correct
30 Correct 49 ms 49912 KB Output is correct
31 Correct 49 ms 49896 KB Output is correct
32 Correct 57 ms 49784 KB Output is correct
33 Correct 2355 ms 201512 KB Output is correct
34 Correct 2157 ms 171652 KB Output is correct
35 Correct 1816 ms 142416 KB Output is correct
36 Correct 1307 ms 101428 KB Output is correct
37 Correct 573 ms 89272 KB Output is correct
38 Correct 531 ms 78260 KB Output is correct
39 Correct 597 ms 89168 KB Output is correct
40 Correct 524 ms 78588 KB Output is correct
41 Correct 550 ms 89020 KB Output is correct
42 Correct 507 ms 78392 KB Output is correct
43 Correct 2051 ms 189268 KB Output is correct
44 Correct 2070 ms 193232 KB Output is correct
45 Correct 271 ms 72948 KB Output is correct
46 Correct 396 ms 79924 KB Output is correct
47 Correct 1099 ms 109688 KB Output is correct
48 Correct 2074 ms 155460 KB Output is correct
49 Correct 458 ms 107956 KB Output is correct
50 Correct 439 ms 107696 KB Output is correct
51 Correct 448 ms 109132 KB Output is correct
52 Correct 516 ms 118860 KB Output is correct
53 Correct 520 ms 118532 KB Output is correct
54 Correct 515 ms 119040 KB Output is correct