제출 #570622

#제출 시각아이디문제언어결과실행 시간메모리
570622patrikpavic2가로등 (APIO19_street_lamps)C++17
20 / 100
1107 ms338356 KiB
/** * user: ppavic * fname: Patrik * lname: Pavić * task: street-light * score: 100.0 * date: 2019-07-06 10:35:14.642573 */ #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #include <unordered_map> #include <ext/pb_ds/assoc_container.hpp> #define X first #define Y second #define PB push_back using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef pair < int, int > pii; typedef vector < int > vi; typedef vector < pii > vp; const int NN = 3e5 + 500; const int M = 1e6 + 500; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const int LOG = 19; const int OFF = (1 << LOG); const int SVE = 1e7 + 500; int n, m, POS, K, K2, I, FL; struct node{ int L, R; int sm = 0, sm2 = 0; }; node N[SVE]; int TKO = 1; int loga1[2 * OFF], loga2[2 * OFF]; void update(int cur, int a,int b){ N[cur].sm += K, N[cur].sm2 += K2; //printf("%d %d += %d\n", a, b, k); if(a == b) return; if(I <= (a + b) / 2) { if(N[cur].L == 0) N[cur].L = TKO++; update(N[cur].L, a, (a + b) / 2); return; } if(N[cur].R == 0) N[cur].R = TKO++; update(N[cur].R, (a + b) / 2 + 1, b); } int get(int cur, int a,int b){ if(cur == 0 || a > I) return 0; if(b <= I) { if(!FL) return N[cur].sm; else return POS * N[cur].sm2 - N[cur].sm; } return get(N[cur].L, a, (a + b) / 2) + get(N[cur].R, (a + b) / 2 + 1, b); } inline void dodaj(int x,int y,int k){ y = n - y + 10; x += 10; for(; x < NN; x += x & -x){ if(loga1[x] == 0) loga1[x] = TKO++; I = y, K = k, K2 = 0; update(loga1[x], 0, OFF - 1); } } inline int nadi(int x,int y){ y = n - y + 10; x += 10; int ret = 0; for(; x ; x -= x & -x){ I = y, FL = 0; ret += get(loga1[x], 0, OFF - 1); } //printf("ret = %d\n", ret); return ret; } inline void dodaj2(int x,int y,int k,int k2){ y = n - y + 10; x += 10; for(; x < NN; x += x & -x){ if(loga2[x] == 0) loga2[x] = TKO++; I = y, K = k, K2 = k2; update(loga2[x], 0, OFF - 1); } } inline int nadi2(int x,int y,int k){ y = n - y + 10; x += 10; POS = k; ll ret = 0; for(; x ; x -= x & -x){ I = y, FL = 1; ret += get(loga2[x], 0, OFF - 1); } //printf("ret = %d\n", ret); return ret; } set < pii > gr; int A[NN], L[M], R[M], tren[M], c = 0; int nadi_interval(int x){ if(x < 0 || x >= n || !A[x]) return -1; return (gr.lower_bound({x, 0})) -> Y; } void makni_interval(int x, int i){ //printf("Nestaje interval [%d %d], ind = %d tren %d sad %d\n", L[x], R[x], x, tren[x], i); dodaj2(L[x], R[x], -tren[x], -1); dodaj(L[x], R[x], i - tren[x]); gr.erase({R[x], x}); } void dodaj_interval(){ //printf("Dolazi interval [%d %d], ind = %d tren %d\n", L[c], R[c], c, tren[c]); dodaj2(L[c], R[c], tren[c],1); gr.insert({R[c], c}); c++; } int main(){ scanf("%d%d", &n, &m); for(int i = 0;i < n;i++){ char c; scanf(" %c", &c); A[i] = c - '0'; } for(int i = 0;i < n;){ if(!A[i]){ i++; continue; } int j = i; for(; j < n && A[j]; j++); L[c] = i, R[c] = j - 1; tren[c] = 0; dodaj_interval(); i = j; } for(int i = 1;i <= m;i++){ char str[10]; scanf("%s", str); if(str[0] == 'q'){ int l, r; scanf("%d%d", &l, &r); l--, r--, r--; //printf("%d %d %d\n", pas.nadi(l, r), cnt_akt.nadi(l, r), akt.nadi(l, r)); printf("%d\n", nadi(l, r) + nadi2(l, r, i)); } else{ int x; scanf("%d", &x); x--; if(!A[x]){ int lft = nadi_interval(x - 1); int rig = nadi_interval(x + 1); int nL = x, nR = x; if(lft != -1){ nL = L[lft]; makni_interval(lft, i); } if(rig != -1) { nR = R[rig]; makni_interval(rig, i); } L[c] = nL, R[c] = nR; tren[c] = i; dodaj_interval(); } else{ int moj = nadi_interval(x); makni_interval(moj, i); if(L[moj] != x){ L[c] = L[moj], R[c] = x - 1, tren[c] = i; dodaj_interval(); } if(R[moj] != x){ L[c] = x + 1, R[c] = R[moj], tren[c] = i; dodaj_interval(); } } A[x] = !A[x]; } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:141:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
street_lamps.cpp:155:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   char str[10]; scanf("%s", str);
      |                 ~~~~~^~~~~~~~~~~
street_lamps.cpp:157:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |    int l, r; scanf("%d%d", &l, &r); l--, r--, r--;
      |              ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:162:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |    int x; scanf("%d", &x); x--;
      |           ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...