oj.uz

Submission #123638

# Submission time Handle Problem Language Result Execution time Memory
123638 2019-07-01T20:59:47 Z duality Street Lamps (APIO19_street_lamps) C++11
100 / 100
 4756 ms 343736 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[300001],bit2[300001];
struct myset {
    vi sorted;
    vpii events;
    int insert(int x) {
        sorted.pb(x);
        events.pb(mp(x,0));
        return 0;
    }
    int query(int x,int m) {
        sorted.pb(x);
        events.pb(mp(x,m));
        return 0;
    }
    int process() {
        int i,j;
        sort(sorted.begin(),sorted.end());
        sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin());
        for (i = 0; i <= sorted.size(); i++) bit1[i] = bit2[i] = 0;
        for (i = 0; i < events.size(); i++) {
            if (events[i].second == 0) {
                int p = lower_bound(sorted.begin(),sorted.end(),events[i].first)-sorted.begin();
                for (j = p+1; j <= sorted.size(); j += j & (-j)) bit1[j]++,bit2[j] += sorted[p];
            }
            else {
                int p = lower_bound(sorted.begin(),sorted.end(),events[i].first)-sorted.begin();
                LLI a = 0,b = 0;
                for (j = p+1; j > 0; j -= j & (-j)) a += bit1[j],b += bit2[j];
                ans[events[i].first] += events[i].second*(a*events[i].first-b);
            }
        }
        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) {
    if (s == e) {
        tree1[i].process(),tree2[i].process();
        return 0;
    }

    int mid = (s+e) / 2;
    tree1[i].process(),tree2[i].process();
    process(s,mid,2*i+1),process(mid+1,e,2*i+2);
    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);
    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()':
street_lamps.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i <= sorted.size(); i++) bit1[i] = bit2[i] = 0;
                     ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < events.size(); i++) {
                     ~~^~~~~~~~~~~~~~~
street_lamps.cpp:89:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (j = p+1; j <= sorted.size(); j += j & (-j)) bit1[j]++,bit2[j] += sorted[p];
                               ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < events.size(); i++) {
                 ~~^~~~~~~~~~~~~~~
street_lamps.cpp:143: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:145: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:154:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",o);
         ~~~~~^~~~~~~~
street_lamps.cpp:156: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:187: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 91 ms 98936 KB Output is correct
2 Correct 91 ms 98808 KB Output is correct
3 Correct 90 ms 98936 KB Output is correct
4 Correct 91 ms 98956 KB Output is correct
5 Correct 90 ms 98936 KB Output is correct
6 Correct 90 ms 98960 KB Output is correct
7 Correct 90 ms 98936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 157932 KB Output is correct
2 Correct 1101 ms 167344 KB Output is correct
3 Correct 1331 ms 192444 KB Output is correct
4 Correct 2239 ms 263984 KB Output is correct
5 Correct 2508 ms 277932 KB Output is correct
6 Correct 2049 ms 239520 KB Output is correct
7 Correct 3038 ms 342716 KB Output is correct
8 Correct 3038 ms 343736 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 99064 KB Output is correct
2 Correct 102 ms 99128 KB Output is correct
3 Correct 96 ms 99320 KB Output is correct
4 Correct 95 ms 99320 KB Output is correct
5 Correct 1210 ms 169168 KB Output is correct
6 Correct 2479 ms 229380 KB Output is correct
7 Correct 3509 ms 279376 KB Output is correct
8 Correct 4600 ms 330228 KB Output is correct
9 Correct 925 ms 168284 KB Output is correct
10 Correct 1066 ms 177692 KB Output is correct
11 Correct 1064 ms 181452 KB Output is correct
12 Correct 4446 ms 328728 KB Output is correct
13 Correct 4680 ms 329728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 99424 KB Output is correct
2 Correct 95 ms 99320 KB Output is correct
3 Correct 94 ms 99320 KB Output is correct
4 Correct 92 ms 99064 KB Output is correct
5 Correct 4756 ms 341048 KB Output is correct
6 Correct 3695 ms 291776 KB Output is correct
7 Correct 2710 ms 242268 KB Output is correct
8 Correct 1251 ms 171828 KB Output is correct
9 Correct 900 ms 150732 KB Output is correct
10 Correct 617 ms 130612 KB Output is correct
11 Correct 880 ms 150992 KB Output is correct
12 Correct 618 ms 130652 KB Output is correct
13 Correct 866 ms 150784 KB Output is correct
14 Correct 575 ms 130756 KB Output is correct
15 Correct 4350 ms 325464 KB Output is correct
16 Correct 4401 ms 329724 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 98936 KB Output is correct
2 Correct 91 ms 98808 KB Output is correct
3 Correct 90 ms 98936 KB Output is correct
4 Correct 91 ms 98956 KB Output is correct
5 Correct 90 ms 98936 KB Output is correct
6 Correct 90 ms 98960 KB Output is correct
7 Correct 90 ms 98936 KB Output is correct
8 Correct 981 ms 157932 KB Output is correct
9 Correct 1101 ms 167344 KB Output is correct
10 Correct 1331 ms 192444 KB Output is correct
11 Correct 2239 ms 263984 KB Output is correct
12 Correct 2508 ms 277932 KB Output is correct
13 Correct 2049 ms 239520 KB Output is correct
14 Correct 3038 ms 342716 KB Output is correct
15 Correct 3038 ms 343736 KB Output is correct
16 Correct 91 ms 99064 KB Output is correct
17 Correct 102 ms 99128 KB Output is correct
18 Correct 96 ms 99320 KB Output is correct
19 Correct 95 ms 99320 KB Output is correct
20 Correct 1210 ms 169168 KB Output is correct
21 Correct 2479 ms 229380 KB Output is correct
22 Correct 3509 ms 279376 KB Output is correct
23 Correct 4600 ms 330228 KB Output is correct
24 Correct 925 ms 168284 KB Output is correct
25 Correct 1066 ms 177692 KB Output is correct
26 Correct 1064 ms 181452 KB Output is correct
27 Correct 4446 ms 328728 KB Output is correct
28 Correct 4680 ms 329728 KB Output is correct
29 Correct 96 ms 99424 KB Output is correct
30 Correct 95 ms 99320 KB Output is correct
31 Correct 94 ms 99320 KB Output is correct
32 Correct 92 ms 99064 KB Output is correct
33 Correct 4756 ms 341048 KB Output is correct
34 Correct 3695 ms 291776 KB Output is correct
35 Correct 2710 ms 242268 KB Output is correct
36 Correct 1251 ms 171828 KB Output is correct
37 Correct 900 ms 150732 KB Output is correct
38 Correct 617 ms 130612 KB Output is correct
39 Correct 880 ms 150992 KB Output is correct
40 Correct 618 ms 130652 KB Output is correct
41 Correct 866 ms 150784 KB Output is correct
42 Correct 575 ms 130756 KB Output is correct
43 Correct 4350 ms 325464 KB Output is correct
44 Correct 4401 ms 329724 KB Output is correct
45 Correct 489 ms 127616 KB Output is correct
46 Correct 692 ms 138572 KB Output is correct
47 Correct 1840 ms 187844 KB Output is correct
48 Correct 3524 ms 260664 KB Output is correct
49 Correct 1199 ms 185932 KB Output is correct
50 Correct 1148 ms 184524 KB Output is correct
51 Correct 1222 ms 188956 KB Output is correct
52 Correct 1352 ms 205512 KB Output is correct
53 Correct 1264 ms 205568 KB Output is correct
54 Correct 1256 ms 205488 KB Output is correct