oj.uz

답안 #268246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268246 2020-08-16T10:41:34 Z evpipis 가로등 (APIO19_street_lamps) C++11
20 / 100
 5000 ms 25628 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 3e5+5;
set<ii> mys;
int light[len]; // n_len

struct {
    struct inter{
        ii seg;
        int sum, num;

        inter(ii se, int s, int n){
            seg = se;
            sum = s;
            num = n;
        }
    };

    vector<inter> vec;

    void upd(ii seg, int sum, int num){
        vec.pb(inter(seg, sum, num));
    }

    bool contain(ii a, ii b){
        return (a.fi <= b.fi && b.se <= a.se);
    }

    int ask(ii seg, int tim){
        //printf("asked at time %d about seg (%d, %d)\n", tim, seg.fi, seg.se);
        int sum = 0, num = 0;
        for (int j = 0; j < vec.size(); j++)
            if (contain(vec[j].seg, seg))
                sum += vec[j].sum, num += vec[j].num;

        //printf("sum = %d, num = %d\n", sum, num);
        //printf("total sum = %d\n", sum + num*tim);

        return sum + num*tim;
    }
} data;

ii rig(int i){
    auto it = mys.lower_bound(mp(i, 0));
    if (it == mys.end())
        return mp(-1, -1);
    return *it;
}

ii lef(int i){
    auto it = mys.lower_bound(mp(i+1, 0));
    if (it == mys.begin())
        return mp(-1, -1);
    return *(--it);
}

void print(){
    printf("current intervals:");
    for (auto it: mys)
        printf(" (%d, %d)", it.fi, it.se);
    printf("\n");
}

void toggle(int i, int t = 0){
    light[i] ^= 1;

    if (light[i] == 1){
        ii cur = mp(i, i), l = lef(i-1), r = rig(i+1);
        if (l.se+1 == cur.fi){
            // remove l and update data and extend cur
            mys.erase(l);
            data.upd(l, +t, -1);
            cur.fi = l.fi;
        }
        if (cur.se == r.fi-1){
            // remove r and update data and extend cur
            mys.erase(r);
            data.upd(r, +t, -1);
            cur.se = r.se;
        }
        // insert cur and update data
        mys.insert(cur);
        data.upd(cur, -t, +1);
    }
    else{
        ii cur = lef(i), l = mp(cur.fi, i-1), r = mp(i+1, cur.se);
        // remove cur and update data
        mys.erase(cur);
        data.upd(cur, +t, -1);
        if (l.fi <= l.se){
            // insert l and update data
            mys.insert(l);
            data.upd(l, -t, +1);
        }
        if (r.fi <= r.se){
            // insert r and update data
            mys.insert(r);
            data.upd(r, -t, +1);
        }
    }

    //print();
}

int main(){
    int n, q;
    scanf("%d %d ", &n, &q);

    for (int i = 1; i <= n; i++){
        char temp;
        scanf("%c", &temp);
        if (temp == '1')
            toggle(i);
    }

    for (int i = 1; i <= q; i++){
        char str[15];
        scanf("%s", str);
        if (str[0] == 'q'){
            int a, b;
            scanf("%d %d", &a, &b);
            b--;

            printf("%d\n", data.ask(mp(a, b), i));
            //printf("asked for interval (%d, %d)\n", a, b);
        }
        else{
            int pos;
            scanf("%d", &pos);
            toggle(pos, i);
        }

        //printf("%d) ", i);
        //print();
    }
    return 0;
}

Compilation message

street_lamps.cpp: In member function 'int<unnamed struct>::ask(ii, int)':
street_lamps.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<<unnamed struct>::inter>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int j = 0; j < vec.size(); j++)
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |     scanf("%d %d ", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         scanf("%c", &temp);
      |         ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         scanf("%s", str);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:136:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |             scanf("%d", &pos);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5028 ms 3896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3164 ms 25628 KB Output is correct
6 Execution timed out 5040 ms 9664 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 5044 ms 9832 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Execution timed out 5028 ms 3896 KB Time limit exceeded
9 Halted 0 ms 0 KB -