이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 500;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
char c = gc(); bool neg = false;
for(; c < '0'||'9' < c; c = gc())
if(c == '-') neg=true;
x = c - '0'; c = gc();
for(; '0' <= c && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c - '0');
if(neg) x = -x;
}
int n, t, last_ans;
int lf[MX], rg[MX], len[MX], cnt_id = 0;
bool cmp(int a, int b){
return len[a] < len[b];
}
int isect(int l1, int r1, int l2, int r2){
return max(min(r1, r2) - max(l1, l2) + 1, 0);
}
struct dat{
vector<int> pend, all;
vector<int> BL[BLOCK], BR[BLOCK];
void add(int id){
pend.push_back(id);
if(pend.size() >= BLOCK){
vector<int> tmp(pend.size() + all.size());
sort(pend.begin(), pend.end());
merge(pend.begin(), pend.end(), all.begin(), all.end(), back_inserter(tmp));
all = tmp; pend.clear();
for(int bl = 0; bl * BLOCK < all.size(); bl ++)
BL[bl].clear(), BR[bl].clear();
for(int i = 0; i < all.size(); i ++){
int bl = i / BLOCK;
BL[bl].push_back(lf[i]);
BR[bl].push_back(rg[i]);
}
for(int bl = 0; bl * BLOCK < all.size(); bl ++)
sort(BL[bl].begin(), BL[bl].end()),
sort(BR[bl].begin(), BR[bl].end());
}
}
int get(int l, int r, int k){
int res = 0;
if(r - l + 1 < k) return 0;
for(int i = 0; i < pend.size(); i ++)
if(isect(lf[pend[i]], rg[pend[i]], l, r) >= k)
res ++;
for(int bl = 0; bl * BLOCK < all.size(); bl ++){
int st = bl * BLOCK, ed = min(st + BLOCK - 1, (int)all.size() - 1);
if(len[all[st]] >= k){
res += ed - st + 1;
res -= BL[bl].end() - upper_bound(BL[bl].begin(), BL[bl].end(), r - k + 1);
res -= lower_bound(BR[bl].begin(), BR[bl].end(), l + k - 1) - BR[bl].begin();
}else if(len[all[ed]] >= k){
for(int i = st; i <= ed; i ++)
if(isect(lf[pend[i]], rg[pend[i]], l, r) >= k)
res ++;
}
}
return res;
}
} active, deleted;
int main(){
cin(n); cin(t);
for(int tp, l, r, k; n --;){
cin(tp);
if(tp == 1){
cin(l); cin(r);
l ^= (t * last_ans);
r ^= (t * last_ans);
if(l > r) swap(l, r);
cnt_id ++;
lf[cnt_id] = l, rg[cnt_id] = r;
len[cnt_id] = r - l + 1;
active.add(cnt_id);
}else if(tp == 2){
cin(k);
deleted.add(k);
}else{
cin(l); cin(r); cin(k);
l ^= (t * last_ans);
r ^= (t * last_ans);
if(l > r) swap(l, r);
last_ans = active.get(l, r, k) - deleted.get(l, r, k);
printf("%d\n", last_ans);
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp: In member function 'void dat::add(int)':
segments.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int bl = 0; bl * BLOCK < all.size(); bl ++)
| ~~~~~~~~~~~^~~~~~~~~~~~
segments.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < all.size(); i ++){
| ~~^~~~~~~~~~~~
segments.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int bl = 0; bl * BLOCK < all.size(); bl ++)
| ~~~~~~~~~~~^~~~~~~~~~~~
segments.cpp: In member function 'int dat::get(int, int, int)':
segments.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < pend.size(); i ++)
| ~~^~~~~~~~~~~~~
segments.cpp:80:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int bl = 0; bl * BLOCK < all.size(); bl ++){
| ~~~~~~~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |