読者です 読者をやめる 読者になる 読者になる

Yandex qual

全然更新してねえ… 簡単なやつで更新しよう
A.やるだけ
B.やるだけ
C.やるだけ
D.
segtreeをかく→TLE→BITをかく→TLE→ゆるして
Challenge Phase

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
int x[100000],y[100000],bit[100001],p=100000000,n;
vector<int> vx,vy;
int query(int id){
	int mn=p;
	while(id>0){
		mn=min(mn,bit[id]);
		id-=(id& -id);
	}
	return mn;
}
void update(int id,int x){
	while(id<=n){
		bit[id]=min(bit[id],x);
		id+=(id& -id);
	}
}
int main(){
	scanf("%d",&n);
	rep(i,n){
		scanf("%d%d",&x[i],&y[i]);
		vx.push_back(x[i]);
		vy.push_back(y[i]);
	}
	sort(all(vx));
	sort(all(vy));
	vx.erase(unique(all(vx)),vx.end());
	vy.erase(unique(all(vy)),vy.end());
	rep(i,n){
		x[i]=find(all(vx),x[i])-vx.begin();
		y[i]=find(all(vy),y[i])-vy.begin();
	}
	rep1(i,n) bit[i]=p;
	rep(i,n){
		if(query(x[i]+1)<=y[i]){
			cout << "Invisible paper detected" << endl;
			return 0;
		}
		update(x[i]+1,y[i]);
	}
	cout << "Well done" << endl;
	return 0;
}

E.
数列の,連続する部分和の最大を求める
これまで(別に変更がなくても)segtreeを書いていた気がしていて、普通にO(n)でできることに気づいた
左から見ていき、その場所(値a)から左に伸ばした時の最大値(mxlとおく),そこまででの部分和の最大(mx)とおく とすると、mxl=max(0,mxl+a),mx=max(mx,mxl)となる
これまでなんで気づかなかったんだろう
F.
[rem]getline(cin,s)と書けば" "ごと読み込める
s.insert(i,t)でs[0]..s[i-1],t[0]..t[t.size()-1],s[i]...となる

[rem]と書いてあるのは自分用のメモ