Table of Contents
A.Gabriel and Caterpillar
B. z-sort
C. Foe Pairs
D. Nested Segments
A. Gabriel and Caterpillar
Solution: Based on the simulation of the question, I personally feel that 1400 points is on the high side and 1000 points is more appropriate.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PII;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;
template <int T>
struct ModInt {
const static int MD = T;
int x;
ModInt(LL x = 0)
: x(x % MD) {}
int get() { return x; }
ModInt operator + (const ModInt & amp; that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt & amp; that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt & amp; that) const {
return ModInt((long long)x * that.x % MD);
}
ModInt operator/(const ModInt & amp; that) const {
return *this * that.inverse();
}
void operator + =(const ModInt & amp; that) {
x + = that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt & amp; that) {
x -= that.x;
if (x < 0)
x + = MD;
}
void operator*=(const ModInt & amp; that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt & amp; that) { *this = *this / that; }
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u + = MD;
return u;
}
friend ostream & amp; operator<<(ostream & amp; os, ModInt x) {
os << x.get();
return os;
}
};
const int mod=998244353;
typedef ModInt<mod> mint;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
int h1,h2,a,b;
cin>>h1>>h2>>a>>b;
int dy=0;
if((h1 + a*8)<h2){
h1 + =a*8;
}else{
cout<<dy<<'\\
';
return;
}
dy + + ;
h1-=12*b;
if(a<=b) {
cout<<-1<<'\\
';
return;
}
while(h1<h2){
if(h1 + a*4<h2){
h1 + =a*4;
if(h1 + a*8>=h2){
cout<<dy<<'\\
';
return;
}else{
h1 + =a*8;
}
}else{
cout<<dy<<'\\
';
return;
}
h1-=b*12;dy + + ;
}
cout<<dy<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}
B. z-sort
Solution: Array sorting, you can find that there is a solution to any situation, just exchange the even numbered bit with its next bit.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PII;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;
template <int T>
struct ModInt {
const static int MD = T;
int x;
ModInt(LL x = 0)
: x(x % MD) {}
int get() { return x; }
ModInt operator + (const ModInt & amp; that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt & amp; that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt & amp; that) const {
return ModInt((long long)x * that.x % MD);
}
ModInt operator/(const ModInt & amp; that) const {
return *this * that.inverse();
}
void operator + =(const ModInt & amp; that) {
x + = that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt & amp; that) {
x -= that.x;
if (x < 0)
x + = MD;
}
void operator*=(const ModInt & amp; that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt & amp; that) { *this = *this / that; }
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u + = MD;
return u;
}
friend ostream & amp; operator<<(ostream & amp; os, ModInt x) {
os << x.get();
return os;
}
};
const int mod=998244353;
typedef ModInt<mod> mint;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
int n;cin>>n;
vector<int>ans(n + 1),a,b;
for(int i=1;i<=n;i + + ) {
cin>>ans[i];
}
sort(ans.begin() + 1,ans.end());
for(int i=2;i<=n;i + =2){
if(i + 1<=n) swap(ans[i],ans[i + 1]);
}
for(int i=1;i<=n;i + + ) cout<<ans[i]<<" ";
cout<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}
C. Foe Pairs
Solution: The question is to find the number of all intervals that do not contain hostile relationships. For a given hostile relationship (l, r), the farthest left endpoint satisfied by each right endpoint is l + 1, that is, all endpoints in the interval [l + 1, r] meet the condition, and the position is recorded with array l, Then 1-n enumerates the right endpoints to calculate the contribution of the left endpoint.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PII;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
template <int T>
struct ModInt {
const static int MD = T;
int x;
ModInt(LL x = 0)
: x(x % MD) {}
int get() { return x; }
ModInt operator + (const ModInt & amp; that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt & amp; that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt & amp; that) const {
return ModInt((long long)x * that.x % MD);
}
ModInt operator/(const ModInt & amp; that) const {
return *this * that.inverse();
}
void operator + =(const ModInt & amp; that) {
x + = that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt & amp; that) {
x -= that.x;
if (x < 0)
x + = MD;
}
void operator*=(const ModInt & amp; that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt & amp; that) { *this = *this / that; }
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u + = MD;
return u;
}
friend ostream & amp; operator<<(ostream & amp; os, ModInt x) {
os << x.get();
return os;
}
};
const int mod=998244353;
typedef ModInt<mod> mint;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
int n,m;cin>>n>>m;
vector<int>p(n + 1);
int y;
for(int i=1;i<=n;i + + ){
cin>>y;
p[y]=i;
}
vector<int>a(m),b(m),l(n + 1,1);
vector<PII>res;
int u,v;
for(int i=0;i<m;i + + ){
cin>>u>>v;
int a=p[u],b=p[v];
if(a>b) swap(a,b);
l[b]=max(l[b],a + 1);
}
LL sum=0;
for(int i=1;i<=n;i + + ){
l[i]=max(l[i],l[i-1]);
sum + =i-l[i] + 1;
}
cout<<sum<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}
D. Nested Segments
Solution: The question means that given the l and r values of n line segments, ask how many line segments other than itself can be covered by each line segment. It is not difficult to find that for line segments [l1, r1], [l2, r2], if [l1, r1] can cover [l2, r2], then l1<=l2,r2>=r1 is satisfied. At the beginning, my idea was two-fold The number of line segments that do not meet the conditions is calculated, but the overlapping part cannot be calculated. Therefore, consider sorting first, sorting the left endpoints from large to small, and for the same left endpoint, sorting the right endpoints from small to large. In this way, it can be found that each time you only need to query the number of line segments whose right endpoint is greater than or equal to the current right endpoint. This process can be maintained with a tree array. Then it is found that the data range of l and r is too large, so the right endpoint is discretized. Just do a binary query every time.
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include<stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PII;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1);
template <int T>
struct ModInt {
const static int MD = T;
int x;
ModInt(LL x = 0)
: x(x % MD) {}
int get() { return x; }
ModInt operator + (const ModInt & amp; that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt & amp; that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt & amp; that) const {
return ModInt((long long)x * that.x % MD);
}
ModInt operator/(const ModInt & amp; that) const {
return *this * that.inverse();
}
void operator + =(const ModInt & amp; that) {
x + = that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt & amp; that) {
x -= that.x;
if (x < 0)
x + = MD;
}
void operator*=(const ModInt & amp; that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt & amp; that) { *this = *this / that; }
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u + = MD;
return u;
}
friend ostream & amp; operator<<(ostream & amp; os, ModInt x) {
os << x.get();
return os;
}
};
const int mod=998244353;
typedef ModInt<mod> mint;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int tr[N],n,m;//tree array
vector<pair<int,PII>>q;
vector<int>v;
int lowbit(int x) {return x & amp;-x;}
int sum(int x){//The subscript is the prefix sum of x
int res=0;
for(int i=x;i;i-=lowbit(i)){
res + =tr[i];
}
return res;
}
void add(int x,int c){//Add c to x position
for(int i=x;i<=m;i + =lowbit(i)){
tr[i] + =c;
}
}
int find(int x){
int l=0,r=v.size()-1;
while(l<r){
int mid=(l + r + 1)>>1;
if(v[mid]<=x)l=mid;
else r=mid-1;
}
return l + 1;
}
void solve()
{
int n;cin>>n;
int l,r;
for(int i=1;i<=n;i + + ){
cin>>l>>r;
q.push_back({i,{l,r}});
v.push_back(r);
}
sort(q.begin(),q.end(),[ & amp;](pair<int,PII>a,pair<int,PII>b){
if(a.second.first!=b.second.first) return a.second.first>b.second.first;
else return a.second.second<b.second.second;
});
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());//Remove duplicates
m=v.size();
vector<int>ans(n + 1);
for(auto t:q){
ans[t.first]=sum(find(t.second.second));
add(find(t.second.second),1);
}
for(int i=1;i<=n;i + + ) cout<<ans[i]<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56,110 people are learning the system