oj.uz

답안 #257735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257735 2020-08-04T16:38:25 Z 2qbingxuan 가로등 (APIO19_street_lamps) C++14
20 / 100
 5000 ms 14716 KB 
#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template<typename H, typename ...T>
void qqbx(const char *s, const H h, T ...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if constexpr(sizeof...(T)) qqbx(++s, args...);
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
typedef int64_t ll;
const int N = 300025;
const int inf = 1e9;

int n, q;
bool light[N];
map<pair<int,int>,int> last;
vector<tuple<int,int,int>> sg;
void add(int L, int R, int d) {
    sg.pb(L, R, d);
}
void toggle(int x, int now) {
    auto &mp = last;
    light[x] = !light[x];
    if(light[x]) {
        int l = x, r = x;
        if(x-1 >= 0 && light[x-1]) {
            auto it = prev(mp.lower_bound({x, 0}));
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            l = L;
            mp.erase(it);
        }
        if(x+1 < n && light[x+1]) {
            auto it = mp.upper_bound({x, inf});
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            r = R;
            mp.erase(it);
        }
        mp[{l, r}] = now;
    } else {
        auto it = prev(mp.upper_bound({x, inf}));
        auto [L, R] = it->first;
        add(L, R, now - it->second);
        mp.erase(it);
        if(L <= x-1) mp[{L, x-1}] = now;
        if(R >= x+1) mp[{x+1, R}] = now;
    }
}
int query(int a, int b, int now) {
    --b;
    int ans = 0;
    {
        if(light[a]) {
            auto it = prev(last.upper_bound({a, inf}));
            auto [l, r] = it->first;
            if(l <= a && b <= r) ans += now - it->second;
        }
    }
    for(auto [l, r, d]: sg) {
        if(l <= a && b <= r)
            ans += d;
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> n >> q >> s;
    for(int i = 0; i < n; i++) if(s[i] == '1') toggle(i, 0);
    for(int now = 1; now <= q; now++) {
        char com[7];
        cin >> com;
        if(com[0] == 'q') {
            int a, b;
            cin >> a >> b;
            --a, --b;
            cout << query(a, b, now) << '\n';
        } else if(com[0] == 't') {
            int x;
            cin >> x;
            --x;
            toggle(x, now);
        }
    }
}

Compilation message

street_lamps.cpp: In function 'void toggle(int, int)':
street_lamps.cpp:36:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:43:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:51:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [L, R] = it->first;
              ^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:64:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [l, r] = it->first;
                  ^
street_lamps.cpp:68:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [l, r, d]: sg) {
              ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 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 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 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 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Execution timed out 5061 ms 2644 KB Time limit exceeded
9 Halted 0 ms 0 KB -