oj.uz

답안 #170159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170159 2019-12-24T06:20:45 Z arnold518 가로등 (APIO19_street_lamps) C++14
20 / 100
 2106 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, Q, A[MAXN+10];

set<int> S, E;
pii range(int x) { return pii(*(--S.upper_bound(x)), *E.lower_bound(x)); }

pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }

struct Node1
{
    pll val;
    Node1 *lc, *rc;
    Node1() : lc(NULL), rc(NULL) {}
};

struct Node2
{
    Node1 *val;
    Node2 *lc, *rc;
    Node2() : val(NULL), lc(NULL), rc(NULL) {}
};

void update1(Node1 *node, int tl, int tr, int x, pll val)
{
    node->val=node->val+val;
    if(tl==tr) return;
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x, val);
    }
}

pll query1(Node1 *node, int tl, int tr, int l, int r)
{
    if(tr<l || r<tl) return pll(0, 0);
    if(l<=tl && tr<=r) return node->val;
    int mid=tl+tr>>1;
    pll ret(0, 0);
    if(node->lc!=NULL) ret=ret+query1(node->lc, tl, mid, l, r);
    if(node->rc!=NULL) ret=ret+query1(node->rc, mid+1, tr, l, r);
    return ret;
}

void update2(Node2 *node, int tl, int tr, int y, int x, pll val)
{
    if(node->val==NULL) node->val=new Node1();
    update1(node->val, 1, N, x, val);
    if(tl==tr) return;
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x, val);
    }
}

pll query2(Node2 *node, int tl, int tr, int yl, int yr, int xl, int xr)
{
    if(yr<tl || tr<yl) return pll(0, 0);
    if(yl<=tl && tr<=yr) return query1(node->val, 1, N, xl, xr);
    int mid=tl+tr>>1;
    pll ret(0, 0);
    if(node->lc!=NULL) ret=ret+query2(node->lc, tl, mid, yl, yr, xl, xr);
    if(node->rc!=NULL) ret=ret+query2(node->rc, mid+1, tr, yl, yr, xl, xr);
    return ret;
}

Node2 *root=new Node2();

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%1d", &A[i]);

    set<int>::iterator it, jt;
    for(i=1; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
    for(i=1; i<=N; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);

    for(it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update2(root, 1, N, *jt, *it, pll(Q+1, 1));

    for(i=1; i<=Q; i++)
    {
        char st[10];
        int a, b;

        scanf("%s", st);
        if(st[0]=='t')
        {
            scanf("%d", &a);

            if(A[a]==0)
            {
                if(S.find(a+1)!=S.end() && E.find(a-1)!=E.end())
                {
                    update2(root, 1, N, range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    update2(root, 1, N, range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    E.erase(a-1);
                }
                else if(S.find(a+1)!=S.end())
                {
                    update2(root, 1, N, range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    S.insert(a);
                }
                else if(E.find(a-1)!=E.end())
                {
                    update2(root, 1, N, range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    E.erase(a-1);
                    E.insert(a);
                }
                else
                {
                    S.insert(a);
                    E.insert(a);
                }
                update2(root, 1, N, range(a).second, range(a).first, pll((Q-i+1), 1));
                A[a]=1;
            }
            else
            {
                int s, e;
                tie(s, e)=range(a);

                update2(root, 1, N, range(a).second, range(a).first, pll(-(Q-i+1), -1));
                if(s==e)
                {
                    S.erase(a);
                    E.erase(a);
                }
                else if(s==a)
                {
                    S.erase(a);
                    S.insert(a+1);
                    update2(root, 1, N, range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                else if(e==a)
                {
                    E.erase(a);
                    E.insert(a-1);
                    update2(root, 1, N, range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                }
                else
                {
                    S.insert(a+1);
                    E.insert(a-1);
                    update2(root, 1, N, range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                    update2(root, 1, N, range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                A[a]=0;
            }
        }
        else
        {
            scanf("%d%d", &a, &b); b--;
            pll ret=query2(root, 1, N, b, N, 1, a);
            printf("%lld\n", ret.first-ret.second*(Q-i+1));
        }
    }
}

Compilation message

street_lamps.cpp: In function 'void update1(Node1*, int, int, int, pll)':
street_lamps.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'pll query1(Node1*, int, int, int, int)':
street_lamps.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'void update2(Node2*, int, int, int, int, pll)':
street_lamps.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'pll query2(Node2*, int, int, int, int, int, int)':
street_lamps.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:92:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp:94: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:95:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%1d", &A[i]);
                         ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", st);
         ~~~~~^~~~~~~~~~
street_lamps.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~
street_lamps.cpp:177:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b); b--;
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 4876 KB Output is correct
2 Correct 530 ms 5812 KB Output is correct
3 Correct 1399 ms 22820 KB Output is correct
4 Runtime error 1406 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1912 KB Output is correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 6 ms 1656 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Runtime error 2106 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 5 ms 1532 KB Output is correct
3 Correct 6 ms 1784 KB Output is correct
4 Correct 8 ms 1912 KB Output is correct
5 Correct 1493 ms 493196 KB Output is correct
6 Runtime error 1235 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 377 ms 4876 KB Output is correct
9 Correct 530 ms 5812 KB Output is correct
10 Correct 1399 ms 22820 KB Output is correct
11 Runtime error 1406 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -