답안 #121341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121341 2019-06-26T11:38:44 Z WhipppedCream 가로등 (APIO19_street_lamps) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
    
const int maxn = 3e5+5;
    
int st[4*maxn];
int arr[maxn];
char s[maxn];
int n;
    
int ask(int i, int j, int p = 1, int L = 1, int R = n)
{
    if(i> R || j< L) return 0;
    if(i<= L && R<= j) return st[p];
    int M = (L+R)/2;
    int x = ask(i, j, 2*p, L, M);
    int y = ask(i, j, 2*p+1, M+1, R);
    return x+y;
}
    
void update(int x, int dx, int p = 1, int L = 1, int R = n)
{
    if(x> R || x< L) return;
    if(L == R)
    {
        st[p] = dx;
        return;
    }
    int M = (L+R)/2;
    update(x, dx, 2*p, L, M);
    update(x, dx, 2*p+1, M+1, R);
    st[p] = st[2*p]+st[2*p+1];
}
    
int q;
   
int A[maxn], B[maxn];
   
vector<int> buck[maxn];
vector<int> tree[4*maxn];
vector<int> ms[4*maxn];
   
void prep(int x1, int y1, int x2, int y2)
{
    buck[x1].pb(y1);
    buck[x2+1].pb(y1);
    buck[x1].pb(y2+1);
    buck[x2+1].pb(y2+1);
}
   
void build(int p = 1, int L = 1, int R = n+1)
{
    if(L == R)
    {
        tree[p] = buck[L];
        sort(tree[p].begin(), tree[p].end());
        tree[p].erase(unique(tree[p].begin(), tree[p].end()), tree[p].end());
        // printf("[%d %d]: ", L, R);
        // for(int x : tree[p]) printf("%d ", x);
        // printf("\n");
        ms[p].assign(tree[p].size()+2, 0);
        return;
    }
    int M = (L+R)/2;
    build(2*p, L, M);
    build(2*p+1, M+1, R);
    int x = 0, y = 0;
    vector<int> &vL = tree[2*p];
    vector<int> &vR = tree[2*p+1];
    while(x< vL.size() && y< vR.size())
    {
        int go;
        if(vL[x]< vR[y])
        {
            go = vL[x];
            x++;
        }   
        else
        {
            go = vR[y];
            y++;
        }
        if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
    }
    while(x< vL.size())
    {
        int go = vL[x];
        x++;
        if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
    }
    while(y< vR.size())
    {
        int go = vR[y];
        y++;
        if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
    }
    ms[p].assign(tree[p].size()+2, 0);
    // printf("[%d %d]: ", L, R);
    // for(int x : tree[p]) printf("%d ", x);
    // printf("\n");
}
   
void updatems(int x, int y1, int y2, int dx, int p = 1, int L = 1, int R = n+1)
{
    if(x< L || x> R) return;
    int pos = lower_bound(tree[p].begin(), tree[p].end(), y)-tree[p].begin();
    for(int k = pos+1; k<= tree[p].size(); k += k & (-k)) ms[p][k] += dx;
    if(L == R) return;
    int M = (L+R)/2;
    updatems(x, y, dx, 2*p, L, M);
    updatems(x, y, dx, 2*p+1, M+1, R);
}
   
int askms(int x1, int y1, int x2, int y2, int p = 1, int L = 1, int R = n+1)
{
    if(x1> R || x2< L) return 0;
    if(x1<= L && R<= x2)
    {
        int res = 0;
        int pos = upper_bound(tree[p].begin(), tree[p].end(), y2)-tree[p].begin()-1;
        for(int k = pos+1; k; k -= k&(-k)) res += ms[p][k];
        return res;
    }
    int M = (L+R)/2;
    int x = askms(x1, y1, x2, y2, 2*p, L, M);
    int y = askms(x1, y1, x2, y2, 2*p+1, M+1, R);
    return x+y;
}
void updateme(int x1, int y1, int x2, int y2, int dx)
{
    updatems(x1, y1, y2+1, dx);
    updatems(x2+1, y1, y2+1, -dx);
}
   
int askpong(int x, int y)
{
    return askms(1, 1, x, y);
}
   
bool con(int a, int b)
{
    return ask(a, b-1) == b-a;
}
    
void toggle(int x, int tim, bool upd)
{
    int lo = 1, hi = x;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(con(mid, x)) hi = mid;
        else lo = mid+1;
    }
    int L = lo;
    lo = x+1, hi = n+1;
    while(lo< hi)
    {
        int mid = (lo+hi+1)/2;
        if(con(x+1, mid)) lo = mid;
        else hi = mid-1;
    }
    int R = lo;
    if(!upd)
    {
        prep(L, x+1, x, R);
    }
    if(arr[x])
    {
        arr[x] = 0;
        if(upd) updateme(L, x+1, x, R, tim);
    }
    else
    {
        arr[x] = 1;
        if(upd) updateme(L, x+1, x, R, -tim);
        // printf("go %d %d %d %d %d\n", L, x+1, x-1, R, -tim);
    }
    update(x, arr[x]);
}
    
int main()
{
    scanf("%d %d", &n, &q);
    scanf("%s", s+1);
    for(int i = 1; i<= n; i++)
    {
        if(s[i] == '1')
        {
            update(i, 1);
            arr[i] = 1;
        }
    }
    for(int tim = 1; tim<= q; tim++)
    {
        A[tim] = B[tim] = -1;
        char t[10];
        scanf("%s", t+1);
        if(t[1] == 't')
        {
            scanf("%d", &A[tim]);
        }
        else
        {
            scanf("%d %d", &A[tim], &B[tim]);
        }
    }
    for(int tim = 1; tim<= q; tim++)
    {
        if(B[tim] == -1)
        {
            int x = A[tim];
            toggle(x, tim, 0);
        }
    }
    build();
    memset(arr, 0, sizeof arr);
    memset(st, 0, sizeof st);
    for(int i = 1; i<= n; i++)
    {
        if(s[i] == '1')
        {
            update(i, 1);
            arr[i] = 1;
        }
    }
    for(int tim = 1; tim<= q; tim++)
    {
        if(B[tim] == -1) 
        {
            int x = A[tim];
            toggle(x, tim, 1);
            continue;
        }
        int x = A[tim], y = B[tim];
        bool cc = con(x, y);
        if(cc) printf("%d\n", tim+askpong(x, y));
        else printf("%d\n", askpong(x, y));
    }
}

Compilation message

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:77:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(x< vL.size() && y< vR.size())
           ~^~~~~~~~~~~
street_lamps.cpp:77:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(x< vL.size() && y< vR.size())
                           ~^~~~~~~~~~~
street_lamps.cpp:92:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(x< vL.size())
           ~^~~~~~~~~~~
street_lamps.cpp:98:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(y< vR.size())
           ~^~~~~~~~~~~
street_lamps.cpp: In function 'void updatems(int, int, int, int, int, int, int)':
street_lamps.cpp:113:59: error: 'y' was not declared in this scope
     int pos = lower_bound(tree[p].begin(), tree[p].end(), y)-tree[p].begin();
                                                           ^
street_lamps.cpp:114:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = pos+1; k<= tree[p].size(); k += k & (-k)) ms[p][k] += dx;
                        ~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:190: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:191:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s+1);
     ~~~~~^~~~~~~~~~~
street_lamps.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", t+1);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:207:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[tim]);
             ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:211:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &A[tim], &B[tim]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~